2.1 시간 복잡도란?
2.1.1 빅오 표기법
알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력간의 상관관계를 표기
2.1.2 시간 복잡도 그래프
알고리즘과 시간 복잡도
| 알고리즘 | 시간 복잡도 |
|---|---|
| 이진 탐색 | O(logN) |
| 선형 탐색 | O(N) |
| 정렬 | O(N logN) |
| 조합 | O(2^n) |
| 순열 | O(N!) |
| 시간 복잡도별 N 크기에 따른 계산 결과(정수로 반올림) |
| 10 | 20 | 100 | 10,000 | 10,000,000 | 10,000,000,000 | |
|---|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 1 | 1 |
| O(logN) | 3 | 4 | 7 | 13 | 20 | 27 |
| O(N) | 10 | 20 | 100 | 10,000 | 10,000,000 | 10,000,000,000 |
| O(N logN) | 33 | 86 | 664 | 132,877 | - | - |
| O(2^N) | 1,024 | - | - | - | - | - |
| O(N!) | 3,628,800 | - | - | - | - | - |
O(logN)은 log2 N을 나타낼 때가 많다. 여기 결과도 log2 N의 결과
2.1.3 입력 데이터 개수별 사용 가능한 시간 복잡도 알고리즘
이처럼 시간 복잡도는 프로그램 실행 시간 결정짓는 중요한 요소. 자기가 작성한 풀이의 시간 복잡도 따져보는견 필연적. 1초라는 제한이 있을때 어느정도 복잡도여야 될까?
조건에 명시되어 있는 최악의 경우를 시간 복잡도에 대입해 보았을때 1억 이 넘지 않는다면 실행시간이 1초보다 빠른 충분히 효율적인 코드일 가능성 높다.
1억이 절대적 기준은 아님. 단, 코테에서는 애매하게 1억 근처에서 계산되는 경우 거의 없을 것. 대부분 1억보다 한참 아래 또는 훨씬 넘을 것.
2.2.2 시간 복잡도를 줄이는 방법
| N | 유추 가능한 시간 복잡도 | 유추 가능한 알고리즘 |
|---|---|---|
| 10 | O(N!) | 순열 |
| 20 | O(2^N) | 조합 |
| 1000~ | O(N^3), O(N^3 logN) | 완전 탐색, 이진 탐색 |
| 10000~ | O(N logN) | 정렬, 이진 탐색 |