알고리즘의 성능을 간결히 나타내기
Big-Oh 만 알고 있으면 안된다!
상세
러닝타임에 대해선 시간 복잡도 (Time complexity), 메모리는 공간 복잡도 (Space complexity) 라고 한다.
가장 많이 쓰는 Big-Oh notation 의 수학적 정의는 아래와 같다. 러닝 타임 T(n) 이 임의의 큰 n 에 대해
을 항상 만족하는 c 를 찾을 수 있으면
… 라고 한다.
풀어 쓰면 n 이 아무리 커져도 f(n) 이 증가하는 정도보단 작거나 같게 T(n) 이 증가한다는 것. Big-Theta, Big-Omega notation 도 비슷하게 정의되는데, Big-Omega 는 lower bound 을, Big-Theta 는 정확한 점근적 행동을 말해준다. (free factor c_0, c_1 를 사용해 정의한다.)
Big-Oh notation 이 가장 인기가 좋은 이유는 증명에 있어서 upper bound 를 증명한 케이스가 많기도 하고, Big-Theta 만큼이나 유용하기 때문이다. 하지만 알고리즘의 성능을 가장 정확히 설명하는 건 BIg-Theta 이며, 어떤 클래스의 알고리즘의 한계를 설명하는 데 Big-Omega 가 사용되기도 한다.
예시
- 상수 시간 (Constant)
- 해시 테이블에서 원소를 고르는 연산
- 배열에서 인덱싱 하는 연산
- 선형 시간 (Linear)
- 배열을 한 번씩 체크해야 하는 연산
- 로그 시간 (Logarithmic)
- 분할 과정에서 depth 마다 실행되는 경우 (sub problem 하나만 중요한 경우)
- Tree 에서 select 가 가장 유명한 예시.
- 다항식 시간 (Polynomial)
- 단순한 nested loop 의 경우
- n 차원 매트릭스의 경우
- 지수적 시간 (Exponeetial)
- 잘못 짠 피보나치 알고리즘의 경우.
- Depth 마다 연산의 총합이 점점 늘어나는 경우