Algorithm Performance
- 수행 시간, 메모리로 측정한다.
- Empirical analysis
- Theoretical analysis
Empirical Analysis
- 실제 실행하면서 측정
- input에 따라 다르다.
- 같은 환경에서 측정해야 비교 가능.
- Measurement criteria
- 메모리 사용량, 수행 시간
Theoretical Analysis
- 이론값
- Asymptotic bound를 계산한다.
- 최악의 경우를 계산한다.
- 환경에 구애받지 않는다.
- Measurement Criteria
- Space : 알고리즘이 차지하는 메모리 바이트의 양
- Time : 수행 시간. 주로 primitive operations의 갯수로 측정. 하지만 각 operation마다 수행 시간이 다름.
- Algorithm Analysis
- 알고리즘의 pseudocode를 사용한다.
- 모든 가능한 경우의 수를 다 계산.
- 테스트 환경과 무관함.
Pseudocode
- High-level description of an algorithm
- 프로그래밍 언어와 독립적
- 실제 코드보다 간결하고 이해하기 쉬움
- 따라서 디자인 이슈는 신경쓰지 않음
Space Complexity
- 알고리즘 수행에 필요한 메모리양. 주로 upper bound로 정의.
- 데이터 공간은 Computer Architectuer와 Compiler, Implementation에 따라 다르다.
/* implementation에 따라 다른 경우 */
double array1[100]; // 64bits 실수형 데이터공간
int array2[100]; // 32bits 정수형 데이터공간따라서 array1이 array2보다 2배 크다.
dense matrix vs sparse matrix
알고리즘에 따른 Space complexity의 차이는 아래 예시를 들 수 있다.
Dense matrix A : [][4][][][8][][][][1][] -> 10 integers
Sparse matrix B : {(2,4), (5,8), (9,1)} -> 6 integers마치 2차원 격자공간에서 관리할 것인가, 리스트 내 리스트 형태로 관리할 것인가.. 코딩테스트 준비하다보면 정말 많이 겪게되는 고민인듯.
Time Complexity
- 알고리즘 실행에 필요한 시간
- 빠를수록 좋다.
- How to measure?
- Count a particular operation (ex. comparisons in sorting)
- Count the number of steps
- Asymptotic complexity
Primitive Operations
- 알고리즘에 의해 수행되는 기본적인 계산들을 의미. (실제로는 다 다름)
- 수행에 들어가는 시간은 전부 constant라고 가정한다.
- 프로그래밍 언어와 상관없다.
ex) assign a value a <- b
ex) comparison a < b
ex) returning from a method (fn call)
Growth function
- Constant : T(n) = c
- Logarithmic : T(n) = log(n) -> binary search
- Linear : T(n) = c * n
- Others : T(n) = n*log(n) -> divide and conquer approach
- Quadratic : T(n) = n^2 -> bubble sort
- Cubic : T(n) = n^3 -> matrix multiplication
- Polynomial : T(n) = n^k
- Exponential : T(n) = c^n -> 하노이, 피보나치
O-notation
- If and only if there exist positive constants c and n0 such that 0 <= |f(n)| <= c|g(n)| for all n >= n0.
- Upper bound of growth fn. The bound does not need to be tight.
ex)
n^2 - 3n + 2 = O(n^2) and O(n^3)
n^2log(n) - 4log(n) + 2n^2 + 4n - 9 = O(n^2*logn)Θ-notation
- If and only if there exist positive constants c1, c2 and n0 such that 0 <= c1|g(n)| <= |f(n)| <= c2|g(n)| for n >= n0.
Trade-off
- 시간복잡도와 공간복잡도는 서로 종속적이기 때문에 trade-off 존재.
- ex) Dense, Sparse matrix, having int(32bits/4Bytes)
- Dense matrix : Space 4 x 10 | Time O(1)
- Sparse matrix : Space 4 x 6 | Time O(n)
- Dense는 메모리를 더 쓰지만, 접근이 빠름.
- Sparse는 메모리를 덜 쓰지만, 순회해야 접근할 수 있음.
Summary
- 복잡도 분석은 대부분
loop를 검사하는 과정이 필수이다. - growth of functions를 특정짓기 위한 시도.
- Big-O notation은 최악의 경우를 찾는 것으로, 상수나 다른 낮은 차수 텀들을 무시하여 간단하게 조사할 수 있다.
- 컴퓨터 과학자들은 이런 복잡도 관련 클레임을 방어하기 위해 가끔 proofs를 사용한다. (?)
