Efficiency, Analysis and Order

O 빠른 알고리즘 중요성

- 문제 1 : 정렬된 배열에 x 값 찾기

=> Sequential Search vs. Binary Search (Worst Case 경우)

Array Size(n)	Sequential Search	Binary Search
128 (2^7)	128 (2^7)	8
1024 (2^10)	1024 (2^10)	11
1048576 (2^20)	1048576 (2^20)	21
4294967296 (2^32)	4294967296 (2^32)	33

<표> 찾는 횟수

- 문제 2: 피보나치 수열

=> Recursive vs. Iterative Fibonacci

• Recursive Fibonacci 시간 복잡도 : 2^n/2

• Iterative Fibonacci 시간 복잡도 : n+1

입력크기(n)	입력크기(n+1)	입력크기(2^n/2)	수행시간(Iteration)	수행시간(Recursion)
40	41	2^20	41ns	1048μs
60	60	1.1*10^9	61ns	1s
80	81	1.1*10^12	81ns	18min
100	101	1.1*10^15	101ns	13days
120	121	1.1*10^18	121ns	36years
160	161	1.1*10^24	161ns	3.8*10^7years
200	201	1.1*10^30	201ns	4*10^13years

<표> 알고리즘별 수행시간

O 알고리즘 시간복잡도

- 시간 복잡도의 두 가지 인자 : 알고리즘의 입력 크기, 알고리즘의 Basic Operation

- 알고리즘의 입력 크기

• 입력이 얼마나 큰지를 알려주는 지표 값

예) n 개의 배열 정렬하기, n 번째 피보나치, 그래프에선 vertices, edges 개수

- 알고리즘의 Basic Operation

• 알고리즘을 지배하는 연산 부분

예) Search 또는 Sort 알고리즘에서 비교연산, 행렬 곱 알고리즘에서 곱셈 연산

- 시간 복잡도 분석

• 입력 크기에 대해 Basic Operation이 몇 번 수행됐는지

예) 순차 검색 알고리즘의 Worst Case는 n개의 배열이 주어졌을 때, n번의 비교를 함

O 시간 복잡도 종류

- Every Case

• 입력 크기가 고정일 때, 어떠한 상황에서도 Basic Operation이 수행되는 횟수는 언제나 동일한 Case

예) n개 숫자 더하기

<그림> n개 숫자 더하기

=> Basic Operation이 ‘+’ 일 때, 어떠한 상황에도 수행 횟수는 n으로 동일

• 입력 크기가, 어떠한 경우라도 Basic Operation 횟수가 같음

- Non-Every Case

• 입력 크기가 고정일 때, 상황에 따라 Basic Operation 수행 횟수가 다른 Case

예) n개의 숫자 중 x 찾기

<그림> n개 숫자 중 x 찾기

=> 배열의 순서에 따라 x 값을 일찍 찾을 수 늦게 찾을 수 있어, 상황마다 Basic Operation 수행 횟수가 달라짐

• Best Case : Basic Operation 수행횟수가 최소인 경우

• Worst Case : Basic Operation 수행횟수가 최대인 경우

• Average Case : Basic Operation 수행횟수가 평균인 경우

O 차수(Order)

- 알고리즘이 얼마나 복잡한지를 정량적으로 다루기 위한 개념

- 알고리즘 A의 시간 복잡도가 0.1n^2이고, 알고리즘 B의 시간 복잡도가 1000n이면 어떤 알고리즘이 더 좋은가? => n 값에 따라 다름

- 그래도... 어떤 알고리즘이 더 좋은지 척도가 있어야? => 입력 크기 n이 매우 크다고 가정하고 비교함

- 빅오(O) 표기법

• 입력 크기 n에 대하여 Basic Operation 횟수를 빅오로 표기하면? 최고차항의 차수!

예) 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 + 3n^2 + 2n + 1 => O(n^3)

• 알고리즘 간 성능을 비교할 때 사용

- 시간복잡도 종류

• O(lg n) : 로그(logarithmic)

• O(n) : 1차(linear)

• O(nlg n)

• O(n^2) : 2차(quadratic)

• O(n^3) : 3차(cubic)

• O(2^n) : 지수(exponential)

• O(n!) : factorial

=> O(lg n)<O(n)<O(nlg n)<O(n^2)<O(n^3)<O(2^n)<O(n!)

• O(lg n), O(n), O(nlg n)는 쓸만한 알고리즘

• O(n^2), O(n^3)는 상황에 따라 (입력값이 작아서 봐줄 수 있는 상황) 봐줄만한 알고리즘

• O(2^n), O(n!)는 걍 쓰레기 알고리즘