복잡도
목차
복잡도
복잡도(Complexity)는 컴퓨터 프로그램의 성능을 파악할 수 있는 척도로 사용됩니다. 복잡도에는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있습니다. 일반적으로 빅 오 표기법(Big-O Notation)을 통해 표현합니다. 복잡도를 신경쓰지 않는다면 컴퓨터의 자원을 과도하게 사용해, 사용자로 하여금 프로그램을 사용할 때 불편함을 느끼게 할 수 있습니다. 대표적으로, 시간 복잡도를 전혀 신경쓰지 않고 프로그램을 작성하게 되면 같은 작업을 수행하는 프로그램이라도 작업양에 따라 걸리는 시간이 급격하게 증가합니다. 같은 작업인데 어느 프로그램은 1초만에, 어느 프로그램은 10초가 걸린다면 당연히 더 빠른 프로그램을 사용할 것입니다. 따라서 프로그래머에게 복잡도 계산은 구체적으로는 아니더라도 꼭 해야하는 절차입니다.
시간 복잡도
먼저 복잡도 중 시간 복잡도(Time Complexity)에 대해 알아보겠습니다. 대표적인 시간 복잡도는 다음과 같습니다.
| 시간 복잡도 | |||
|---|---|---|---|
| 이름 | 표기 | 시간 (1,000회 기준) | 예시 |
| 상수 시간 | O(1) | 1 | 정렬된 숫자 배열에서 중위값 찾기 |
| 로그 시간 | O(log n) | 9.97 | 이분 탐색 |
| 선형 시간 | O(n) | 1,000 | 선형 탐색 |
| 선형 로그 시간 | O(n log n) | 9,966 | 비교 정렬 |
| 이차 시간 | O(n2) | 1,000,000 | 버블 정렬, 삽입 정렬 |
| 삼차 시간 | O(n3) | 1,000,000,000 | 일반적인 행렬의 곱셈 |
| 지수 시간 | O(2n) | 약 1.07 × 10301 | 피보나치 수열 |
| 팩토리얼 시간 | O(2n) | 약 4.02 × 102567 | 완전 탐색을 통한 외판원 문제 |