코딩 테스트를 할 때 효율적인 알고리즘을 선택하기 위해서는 시간 복잡도를 보고 선정해야 한다.
시간 복잡도 : 알고리즘의 성능을 나타내는 지표, 입력 크기에 대한 연산 횟수의 상한을 의미한다.
시간 복잡도는 낮으면 낮을수록 좋다.
예를 들어 1차원 배열 검색할 때 값을 가장 빨리 찾는 경우와 값을 가장 늦게 찾는 경우를 살펴보자.
가장 빨리 찾는 경우
찾는 데이터가 데이터 배열에 맨 앞에 있는 경우로 1번만 검색하면 된다.
가장 늦게 찾는 경우
찾는 값이 아예 없거나 맨 뒤에 있는 경우, 연산 횟수는 최대다.
알고리즘 수행 시간을 측정하는 방법
절대 시간을 측정하는 방법과 시간 복잡도를 측정하는 방법이 있다. 주로 코딩 테스트를 할 때 시간 복잡도를 측정하는 방법을 사용한다.
시간 복잡도를 측정한 결과는 최선, 보통, 최악의 경우로 나눈다.
점근적 표기법 : 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법
※ 코딩 테스트에서는 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하므로 시간 복잡도는 최악의 경우를 가정하여 이야기 하는 것이 일반적이다.
최악의 경우 시간 복잡도를 표현하는 빅오 표기법
가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법으로 이 표기법을 빅오 표기법이라고 한다.
※ 상한선은 빅오 표기법, 하한선은 빅오메가 표기법으로 표시한다.
빅오 표기법을 쓸 때는 최고차항만 남기고 계수를 지운다.
다음은 시간 복잡도를 코딩 테스트에 활용하기 위해 정리한 시간 복잡도 테이블이다.
| 시간 복잡도 | N의 가용 범위 |
| O(N!) | 10 |
| O(2ⁿ) | 20~25 |
| O(N³) | 200~300 |
| O(N²) | 3,000 ~ 5,000 |
| O(NlogN) | 100만 |
| O(N) | 1,000 ~ 2000만 |
| O(logN) | 10억 |
예시로 하나하나 짚어가며 찾는 방식은 시간 복잡도가 O(N)이고, O(N)이 허용하는 연산 횟수는 2000만 미만이므로 데이터 개수가 2,000만 개 이하면 이 알고리즘은 사용해도 된다.
이런식으로 시간 복잡도를 활용해 불필요한 알고리즘을 제외할 수 있고, 매우 연습이 필요하므로 아주 쉬운 코딩 테스트 문제에서도
시간 복잡도를 먼저 따져보는 연습이 필요할 것 같다.