Chap 01. 자료구조와 알고리즘의 이해

● 자료구조에 대한 이해

자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명한다.

내가 공부할 자료구조는 선형 자료구조와 비선형 자료구조 이다.

선형 자료구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.
ex) 리스트와 스택, 큐

비선형 자료구조 : 데이터를 나란히 저장하지 않는 구조이다.

자료구조는 '데이터의 표현 및 저장방법'이라 하였다.
그렇다면, 알고리즘은 '문제의 해결 방법'을 뜻한다.

예를들어,

int arr[10] = {1,2,3,4,5,6,7,8,9,10}; for (int i = 0; i < 10; i++)  sum += arr[i];

arr라는 배열로 데이터를 저장하였고(자료구조)
for 반복문으로 배열에 저장된 모든 값의 합을 구하였다.(알고리즘)

---

● 알고리즘의 성능분석 방법

자료구조와 알고리즘을 평가하는 두 가지 요소는 
1. 어떤 상황에서 더 빠른지, 느린지
             속도 => 시간복잡도

2. 어떤 상황에서 메모리를 적게 쓰는지, 많이 쓰는지
메모리의 사용량 => 공간복잡도

일반적으로, 알고리즘을 평가할때 '실행속도'에 초점을 둔다.

'실행속도', 우리는 어떻게 실행속도를 측정할 것인가?
이에 대한 해답으로 우리는 '연산의 횟수'를 세기로 하였다.

알고리즘 성능을 분석하다보면, 운이 좋아 찾고자 하는 값을 바로 찾을 수 도 있고
운이 나빠 찾고자 하는 값을 제일 늦게 찾을 수 도 있다. 이러한 경우를 각각 '최선의 경우'와 '최악의 경우'라고한다.
그러나, 알고리즘을 평가하는데 있어서 우리는 '최악의 경우'만을 판단 할 것이다.

---

● 빅 - 오 표기법

데이터의 수가 n일 때, 비교연산의 횟수를 T(n)이라 한다.

T(n) = n² + 2n + 1  은 n이 증가함에 따라서 2n+1은 미미해지므로 
T(n) = n²로 간략화 할 수 있다. 
이것을 빅-오 표기법으로 표현하면 O(n²)로 표현할 수 있다. 

즉, 최고차항의 차수가 빅-오가 되며, 계수또한 버려준다.

 

 

출처 : 윤성우의 열혈 자료구조