알고리즘의 평균 수행 시간을 측정하기는 매우 어렵다.
입력의 크기나 수행 시간을 측정할 때 컴퓨터마다 컴퓨팅 환경이 다르기 때문이다.
그래서 worst-case 실행시간을 알고리즘 수행시간으로 간주한다.
알고리즘의 효율성을 판단하는 기준으로 7가지 증가율 그래프가 있다. (n은 입력의 크기)
1. 상수(Constant, 1) : 입력에 상관없이 항상 일정한 값을 가진다. 가장 높은 효율을 보이는 이상적인 증가율.
2. (Logarithmic, Log n)
3. (Linear, n)
4. N-Log-N (n log n)
5. Quadratic (n^2)
6. Cubic (n^3)
7. Exponential (2^n)
1. Big-Oh Notation
- 여기서 중요한 점은 "Tighter Upper Bound"라는 것이다.
2. Big-Omega Notation
- Big-Oh의 반대 개념으로 볼 수 있다
- "최소한 이만큼의 시간이 걸린다"의 기준이며
- "Asymptotic lower Bound"
2. Big-Theta Notation