01. [자료구조] 자료구조에 대한 기본적인 이해

 

자료구조란 무엇인가?

 

자료구조 : 데이터의 표현(데이터의 저장) 방법

ex) int, float, vector, list, map, 정적 배열, 동적 배열 등등

 

알고리즘 : 자료구조로 표현된 데이터를 대상으로 하는 '문제 해결 방법'

 

[ 자료구조의 분류 ]

 

 

 

---

 

 

 

알고리즘의 성능분석 방법

[ 시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity) ]

 

 

시간 복잡도 (Main)

"어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가?"

 

공간 복잡도 (Sub)

"어떤 알고리즘이 어떠한 상황에서 메모리를 더 적게 쓰고 많이 쓰나?"

 

 

알고리즘의  수행속도를 평가할 때는 연산의 횟수를 세는 방법을 취한다.

그리고 처리해야 할 데이터의 수가 n에 대한 연산횟수의 함수 T(n)을 구성한다.

 

 

데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.

데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

 

데이터의 양의 적을 경우에는 A알고리즘이 더 빠르지만,

데이터의 수가 기하급수적으로 많아질 경우 B 알고리즘이 훨씬 더 빨라진다.

수행 속도의 변화 정도를 봤을 때, B 알고리즘이 더 빠른 알고리즘이라 할 수 있겠다.

 

 

 

---

 

 

빅-오 표기법 (Big - Oh Notation)

 

T(n)에서 실제로 영향력을 끼치는 부분만을 따지는 것.

 

T(n) = n^2 + 2n + 1

n이 증가함에 따라 2n + 1이 미치는 영향은 미미해지므로

다음과 같이 간략화 할 수 있다.

T(n) = n^2

O(n^2)

 

T(n) = n^2 + 2n + 1의 빅오는 n^2이며,

이는 n의 증가 및 감소에 따른 T(n)의 변화 정도가 n^2의 형태를 띔을 의미한다.

 

 T(n) = n^2 + 2n + 9               -> O(n^2)

T(n) = n^4 + n^3 + n^2 + 1    -> O(n^4)

T(n) = 5n^3 + 2n + 1              -> O(n^3)

 

"T(n)이 다항식으로 표현될 경우, 최고차항의 차수가 빅-오가 된다"

 

 

[ 대표적인 빅-오 ]

 

1. O(l)

상수형 빅-오.

연산횟수가 고정인 유형의 알고리즘.

 

2. O(log n)

로그형 빅-오.

'데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘.

 

 

3. O(n)

선형 빅-오.

데이터의 수와 연산횟수가 비례하는 알고리즘.

 

 

4. O(n^2)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘.

이중 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우 발생.

즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 바람직하지 못함.

 

 

5. O(n^3)

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘.

삼중 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우.

적용하기에는 무리가 있는 알고리즘.

 

 

성능 평가(수행시간, 연산횟수)를 하면 다음과 같다.

O(I) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3)

(로그형 빅-오가 성능이 좋은 알고리즘)