가상컴퓨터에서 가상언어로 작성된 가상코드를 실행한다고 가정할 때, 특정 입력에 대해 수행되는 알고리즘의 기본연산의 횟수로 수행시간을 정의한다.
그러나 모든 입력에 대한 수행시간을 알 수 없기 때문에 최악의 경우의 입력을 가정하여 **최악의 경우의 입력(Worst-Case input)**에 대한 알고리즘의 수행시간을 측정하게 된다.
: 알고리즘의 성능을 수학적으로 표현해주는 표기법으로 시간복잡도, 공간복잡도를 표현할 수 있다.
$$ O(n^2), O(2^n) $$
다음과 같이 승수로 표현되는 알고리즘은 사실상 사용할 수 없는 알고리즘. 그러나 n^2에 해당하는 버블정렬(Bubble Sort) 알고리즘은 가독성도 좋고 코드 작성도 편하기 때문에 자주 사용된다.
$$ O(nlog n), O(log n) $$
보편적으로는 다음의 복잡도를 가지는 알고리즘을 선호한다.
| Big-O 표기법 | 시간복잡도 | 설명 |
|---|---|---|
| O(1) | 상수 | 실행시간은 항상 일정하다. 대표적으로 해시 테이블에서 요소를 찾는 것이 있다. |
| O(n) | 선형 | 실행시간은 입력 크기에 따라 선형적으로 증가한다. 대표적으로 리스트의 모든 원소에 대한 조건을 비교하는 함수가 있다. |
| O(n^2) | 제곱 | 실행시간은 입력 크기의 제곱합수이다. 대표적으로 2중 for 문에서 중복 값을 찾는 함수이다. |
| O(2^n) | 지수 | 실행시간은 입력의 크기에 따라 기하급수적으로 증가한다. 대표적으로 three-coloring problem이 있다. |
| *** 매우 비효율적이기 때문에 잘 사용하지는 않는다.** | ||
| O(log n) | 로그 | 실행시간은 선형적으로 증가한다. 대표적으로 이진탐색이 있다. |
$$ O(n!) > O(c^n) > O(n^3) > O(n^2) > O(nlogn) > O(n) > O(sq) > $$