2.1.2 시간 복잡도 그래프
시간 복잡도는 입력 크기와 실행 시간의 상관관계입니다. 입력 크기가 작다면 연산이 적기 때문에 시간 복잡도가 의미 있는 차이를 만들어 내지 않습니다. 하지만 입력 크기가 커진다면 실행 시간의 차이는 어마어마해집니다.
앞으로 여러 장에 걸쳐 다양한 알고리즘을 살펴볼 것입니다. 알고리즘은 코드가 실행되는 로직이므로 시간 복잡도를 계산할 수 있습니다. 몇 가지 알고리즘의 시간 복잡도를 다음 표에서 살펴봅시다.
▼ 표 2-1 알고리즘과 시간 복잡도
|
알고리즘 |
시간 복잡도 |
|
이진 탐색 |
O(logN) |
|
선형 탐색 |
O(N) |
|
정렬 |
O(N logN) |
|
조합 |
O(2N) |
|
순열 |
O(N!) |
이와 별개로 특별한 로직 없이 실행되는 사칙 연산과 같은 단순 연산의 시간 복잡도는 상수 시간이라고 하며 O(1)로 표기합니다. 앞서 살펴본 O(1), O(logN), O(N), O(N logN), O(N2), O(2N), O(N!) 등이 있습니다. 각 시간 복잡도별로 계산되는 값을 N 값에 따라 살펴봅시다.