time complexity

입력 크기가 커질 때 알고리즘의 실행 시간이 어떤 비율로 늘어나는지를 나타낸 것이다. 초 단위 실행 시간은 기계와 언어에 따라 달라지므로, 대신 기본 연산이 몇 번 일어나는지를 입력 크기 $n$ 의 함수로 센다.

표기

가장 많이 쓰는 것은 big-O 다. $O(f(n))$ 은 충분히 큰 $n$ 에서 실행 횟수가 $f(n)$ 의 상수배를 넘지 않는다는 뜻, 즉 위쪽 한계를 말한다. 상수배와 낮은 차수 항은 버리므로 $3n^2+100n$ 은 $O(n^2)$ 이다.

표기	뜻
$O(f)$	이보다 느리지는 않다 (상한)
$\Omega (f)$	이보다 빠르지는 않다 (하한)
$\Theta (f)$	상한과 하한이 같다

최악·평균·최선

같은 알고리즘도 입력 모양에 따라 걸리는 시간이 다르다. Insertion Sort 는 이미 정렬된 배열에서 $O(n)$ 이지만 역순 배열에서는 $O(n^2)$ 이다. 각 원소가 제자리에서 최대 $k$ 칸 떨어져 있는 배열이라면 $O(kn)$ 으로 끝난다. 그래서 ”$O(n^2)$ 정렬” 이라는 한마디만으로는 그 알고리즘이 언제 유리한지 알 수 없다.

한 번의 연산이 아니라 연산 여러 번의 평균 비용을 따지는 방식은 amortized analysis 에 있다.

흔한 증가율

$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)$

비교 기반 정렬은 $O(n\log n)$ 보다 빠를 수 없다는 하한이 증명돼 있다. $O(2^n)$ 이상이 되면 $n$ 이 조금만 커져도 현실적으로 계산이 끝나지 않는데, 다항 시간 알고리즘이 알려져 있지 않은 문제들의 분류는 NP-complete 를 참고한다.