프로그램 실행 시간은 보통 최악 실행 시간으로 결정한다. 만약 평균 실행 시간으로 한다면 평균을 구하기 위한 실행 시간 케이스들을 모두 모으기가 힘들고, 최선의 실행 시간으로 할 경우 대다수의 케이스에 적용되지 않아서 사용하는 의미가 부족하기 때문이다.
세 가지 표기법
O(n): (Big-Oh) 최악의 실행 시간
Ω(n): (Big-Omega) 최선의 실행 시간
Θ(n): (Big-Theta) Big-Oh식이랑 Big-Omega식이 점근적으로 동일한 경우 Big-Theta로 표기할 수 있다.
보통 Big-Oh 표기를 주로 사용한다.
표기 요령
- 표기할 때는 계수가 없도록 하고 가능한 한 작은 함수를 사용해야 한다.
- 다항식이 있는 경우, 낮은 차수는 없앤다. 예를 들면, 3n^2 + 4n + 5의 실행 시간을 가진 알고리즘의 경우, O(n^2)으로 표기할 수 있다.
참고
- O(1)은 상수 시간이다. 식을 단순히 대입하거나 사칙연산을 하는 등의 작업이 O(1)에 해당한다. O(c)로 표현하기도 한다.
- O(g(n))에서 g(n)의 차수가 늘어나는 경우는 일반적으로 반복문이 사용되는 경우다.
- O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) 순으로 실행시간이 증가한다
예시
- 5n의 경우 O(n)으로 작성할 수 있고 Ω(n)으로도 작성할 수 있으므로, Θ(n)으로도 작성할 수 있다.
- 2n^2 + 3nlogn의 경우 O(n^2), Ω(n^2), Θ(n^2)으로 작성할 수 있다.
- 아래 이중 for문의 바깥 for문은 n회 실행, 내부 for문은 ∑n^2 = n^3회 만큼 실행하므로 O(n^4)
for (int k = 1; k <= n^2; k++)
for (int j = 1; j <= k; j++)