성능측정을 해야하는 이유
알고리즘이 창의적이거나 좋더라도 실행시간이 느리다면 사용하기가 어렵다. 따라서 알고리즘을 만들고 나면 성능을 측정해야한다.
성능측정방법
알고리즘의 성능을 분석하는 방법은 지표가 시간이냐, 공간이냐에 따라 달라진다.
시간복잡도
알고리즘이 문제를 해결하는 데에 걸리는 시간을 시간복잡도라고 한다. 시간을 기준으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 시간복잡도를 측정한다. 시간복잡도는 빅오표기법으로 표현한다.
공간복잡도
알고리즘이 문제를 해결하는 데에 사용하는 메모리량을 공간복잡도라고 한다. 시간을 공간으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 공간복잡도를 측정한다. 공간복잡도도 또한 빅오표기법으로 표현한다.
원본데이터를 기준으로 알고리즘이 문제를 해결하는데 필요한 추가적인 메모리의 양을 나타낸다.
빅오표기법
빅오표기법은 데이터의 크기에 따른 시간·공간의 증가 경향을 표기한다. 복잡도를 오름차순으로 표시하면 다음과 같다.
같은 데이터로 같은 문제를 해결할 때 어떤 알고리즘이 다른 알고리즘보다 복잡도가 낮다면 성능이 더 좋다. 위의 그림에서는 위의 지표로 갈수록 더 효율적인 알고리즘이다.
성능측정 예시: 선형탐색 vs 이진탐색
빨간선이 선형탐색, 파란선이 이진탐색의 시간복잡도를 표현한다. 선형탐색의 시간복잡도는 데이터의 크기에 따라 탐색에 걸리는 시간이 선형적으로 증가하므로 O(N)이다. 이진탐색의 시간복잡도는 데이터의 크기에 따라 탐색에 걸리는 시간이 log형태로 증가하므로 시간복잡도는 O(logN)이다. 따라서 이진탐색은 선형탐색보다 더 효율적이다.
시간복잡도의 활용
해석
코딩테스트에서는 시간복잡도로 알고리즘의 성능을 판단하는 것이 중요하다. 원하는 결과를 출력을 한다고하더라도 시간초과가 발생하면 그 알고리즘은 적합하지 않다. 데이터의 크기와 시간제한을 보고 시간복잡도를 추론한 다음 적합한 알고리즘을 고안해야한다.
아래의 표는 시간 제한 1초를 기준으로 N의 크기에 따른 알고리즘의 적정 시간복잡도를 보여준다.
| N의 크기 | 시간복잡도 |
| N ≤ 11 | O(N!) |
| N ≤ 25 | O(2^N) |
| N ≤ 100 | O(N^4) |
| N ≤ 500 | O(N^3) |
| N ≤ 3,000 | O(N^2logN) |
| N ≤ 5,000 | O(N^2) |
| N ≤ 1,000,000(백만) | O(NlogN) |
| N ≤ 10,000,000(천만) | O(N) |
| N > 10,000,000(천만) | O(logN), O(1) |
활용
시간제한이 1초일 때 데이터 N의 크기가 다음과 같다면 시간복잡도에 대응되는 알고리즘을 사용할 수 있다. 예를 들어, N의 크기가 10인데 시간제한이 1초라면 시간복잡도가 O(N!)인 알고리즘을 사용할 수 있다. 그보다 낮은 시간복잡도를 가진 알고리즘도 물론이다.