알고리즘의 성능 평가
시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 점근적 표기법으로 나타내는 것
점근적 표기법 (Asymptotic Notation)
낮은 계수와 상수를 제거한 복잡도 표기법
- Big-Theta Notation : 평균 복잡도 (평균점근)
- Big-Oh Notation : 최악의 경우 복잡도 (상한점근)
- Big-Omega Notation : 최선의 경우 복잡도 (하한점근)
복잡도 표기시 Big-O를 보편적으로 사용한다.
Big-O 표기법의 대표적인 종류
- Constant Time : O(1)
- Logarithmic Time : O(log n)
- Linear Time : O(n)
- Log Linear Time : O(n log n)
- Quadratic Time : O(n2)
- Cubic Time : O(n3)
- Exponential Time : O(2n)
References
http://bigocheatsheet.com/