알고리즘의 효율성은 빅오표기법으로 많이 표시되는데, 이는 running time complexity가 최악인 case를 측정해서 비교하는 것이다.
Input size가 n이고 c가 양의 상수일 때 Time complexity를 비교하자면 아래와 같다.
| 빅오표기법 | 효율성 | 비고 | 예시 |
|---|---|---|---|
O(1) |
Best🚀 |
Constant Running Time을 갖는 Ideal 알고리즘. n의 크기와 관계 없이 실행 시간이 상수인 경우 | |
O(logn) |
Good👍 |
Logarithmic 알고리즘. n에 대수적으로 비례해서 증가 | Binary Search |
O(n) |
Fair🙂 |
Linear 알고리즘. n에 직접적으로 비례해서 증가 | Linear Search |
O(nlogn) |
Bad🙉 |
Superlinear 알고리즘. n에 비례해서 증가. | Python sort method, Heap Sort, Merge Sort |
O(n^c) |
Worst😱 |
Polynomial 알고리즘. | Bubble sort, Selection sort, Insertion sort |
O(c^n) |
Worst😱 |
Exponential 알고리즘. | Tower of Hanoi |
O(n!) |
☠️ | Factorial 알고리즘. | Brute force for Traveling Salesman |
일반적으로 공간 효율성과 시간 효율성은 Tradeoff가 있다. 머지 소트는 빠르지만 많은 메모리가 필요하고, 버블 소트는 느리지만 메모리를 최소한으로 사용한다. 그러므로 시간 효율성과 공간 효율성이 모두 좋은 알고리즘을 고민하는 것이 중요하다.