알고리즘에 필요한 수고(시간 복잡도)나 기억 영역(공간 복잡도)이 데이터의 수 n에 대해 어떻게 늘어나는지를 나타낸 것. O(n)이나 O(n log n), O(n²) 같은 점근 표기법(빅오 표기법)으로, 계수나 낮은 차수의 항을 생략하여 쓴다.
일본어 명칭: 計算量
시간 복잡도(Time Complexity)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 7개에 나와요.
분야: 자료 구조와 알고리즘
O(f(n))은 n이 충분히 클 때 수고가 대략 f(n)의 상수배 이하에 들어간다는 것을 나타냅니다. 비교 횟수가 3n² + 5n + 2회인 알고리즘은 n이 커지면 n²의 항이 지배적이 되므로 O(n²)으로 씁니다. 자주 나오는 순서로 O(1)(상수), O(log n)(이진 탐색), O(n)(선형 탐색), O(n log n)(병합 정렬, 힙 정렬), O(n²)(버블 정렬, 선택 정렬), O(2ⁿ)(단순한 전수 탐색) 등이 있습니다. n = 1000일 때 log₂ n은 약 10, n log₂ n은 약 1만, n²은 100만이므로, 큰 데이터에서는 차수의 차이가 결정적이 됩니다.
같은 알고리즘이라도 입력에 따라 수고가 달라지는 경우가 있습니다. 삽입 정렬은 정렬된 데이터라면 비교가 n−1회인 O(n)이지만, 역순이면 n(n−1)/2회인 O(n²)입니다. 퀵 정렬은 평균 O(n log n)이지만, 피벗의 선택 방법과 데이터에 따라서는 최악 O(n²)이 됩니다. 응답 시간에 상한이 필요한 시스템에서는 최악의 경우를, 전체 작업량을 어림할 때는 평균의 경우를 중시합니다. 가변 길이 배열에 대한 추가처럼 가끔 무거운 처리가 있어도 여러 번의 평균으로는 일정해지는 것은 분할 상환 시간 복잡도 O(1)로 나타냅니다.
빅오 표기법은 상수배를 무시하므로, 같은 O(n)이라도 실제 속도는 크게 다를 수 있습니다. 현재의 컴퓨터에서는 주기억에 대한 접근이 L1 캐시보다 100배 가까이 느리므로, 배열을 차례로 읽는 처리는 연결 리스트를 따라가는 처리보다 몇 배나 빨라집니다. 또한 n이 작은 범위에서는 차수가 큰 단순한 방법이 더 빠른 경우도 있어, 실제 정렬 구현에서는 짧은 구간에 삽입 정렬을 사용합니다. 성능을 개선할 때는 먼저 차수가 큰 알고리즘을 쓰고 있지 않은지 확인하고, 그다음 메모리 접근 방식 등을 측정하여 다듬어 갑니다.
정답: C. O(n²)
비교하는 쌍의 수는 (n−1) + (n−2) + … + 1 = n(n−1)/2이며, n = 10이면 45회, n = 1000이면 499,500회입니다. 시간 복잡도의 차수는 n이 커졌을 때의 증가 방식만 보므로, 계수 1/2이나 낮은 차수의 항을 생략하여 O(n²)으로 나타냅니다. n이 2배가 되면 횟수는 약 4배가 됩니다. O(n)은 모든 원소를 한 번씩 보기만 하는 처리, O(n log n)은 병합 정렬처럼 절반으로 나누기를 반복하는 처리의 시간 복잡도입니다.
정답: B. 8초
O(n²)에서는 처리 시간이 데이터 수의 제곱에 비례하므로, 데이터 수가 4배가 되면 처리 시간은 4² = 16배가 되어 0.5초 × 16 = 8초입니다. 2초는 데이터 수에 비례하는 O(n)의 경우, 32초는 세제곱에 비례하는 O(n³)의 경우(4³ = 64배)의 값입니다. 실제로는 데이터가 캐시에 다 들어가지 않게 되는 등의 영향으로 이보다 느려지기도 합니다.
밑을 바꿔도 상수배밖에 차이 나지 않으므로(log₂ n = log₁₀ n ÷ log₁₀ 2), 빅오 표기법에서는 밑을 쓰지 않는 것이 보통입니다. 이진 탐색처럼 절반씩 나누는 경우는 실제 횟수가 log₂ n에 가까워집니다.
시간 복잡도는 처리의 수고(실행 시간)가 늘어나는 방식, 공간 복잡도는 필요한 기억 영역이 늘어나는 방식입니다. 병합 정렬은 시간 O(n log n), 작업용 공간 O(n)이고, 힙 정렬은 시간 O(n log n), 공간 O(1)인 것처럼 둘을 함께 비교합니다.
시간 복잡도의 차수는 n이 커졌을 때의 증가 방식만 보므로, 계수 1/2이나 낮은 차수의 항을 생략하여 O(n²)으로 나타냅니다.
원소 수가 n인 배열에서 서로 다른 두 원소의 쌍을 모두 한 번씩 비교하는 처리(i번째 원소를 그보다 뒤에…데이터의 개수는 시간 복잡도와 관계가 없습니다.
퀵 정렬의 시간 복잡도가 O(n²)이 되는 전형적인 경우는?최선의 경우(맨 앞에 있음)는 1회, 최악의 경우(맨 끝에 있음)는 100회이며, 평균도 최악도 n에 비례하므로 시간 복잡도는 O(n)입니다.
서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을…시간 복잡도는 O(log n)이며, 100만 개라도 최대 20회면 됩니다.
오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 …시간 복잡도의 차수가 같더라도 메모리 접근 방식에 따라 실제 속도는 크게 달라집니다.
원소 수가 많고 적재율을 0.5 정도로 유지한 해시 테이블에서, 선형 탐사의 개방 주소법이 체이닝(연결 리…배열(Array) 이진 탐색(Binary Search) 이진 힙(Binary Heap) 중앙값(Median) 해시 테이블(Hash Table) 연결 리스트(Linked List) 캐시 라인(Cache Line) 프리페치(Prefetch) 포인터(Pointer) 깊이 우선 탐색(Depth-First Search)