MAKONEA빅 O 표기법에 대하여
기본적으로 알아두면 좋다
들어가기 앞서서...
우리는 컴퓨터 공학을 배우면서 알고리즘의 성능을 분석하기 위해 Big-O 표기법을 접하게 된다.
대부분 컴퓨터 공학자들은 지루한 사람들이므로 기억이 안 나는게 당연하고 또 대강 이해하면서 넘어 간다.
일반적으로는
“O(1)에 가까울수록 빠르고, O(n!)에 가까울수록 느리다”는 식으로 단순하게 이해하는 경우가 많다.
그렇다면 Big-O의 정확한 정의는 무엇이며, 왜 이러한 표기법이 사용되는 것일까?
(빅 O 표기법)
빅 O 표기법의 시작
빅 O 표기법은 1894년 독일 수학자 파울 바흐만(Paul Bachmann)이 그의 저서 《Analytische Zahlentheorie》(해석적 정수론)에서 처음 소개했고
바흐만은 함수의 성장률을 비교하고 근사적으로 표현하기 위해 이 표기법을 도입했다.
이후 에드문트 란다우(Edmund Landau)가 이 개념을 더욱 정교화하고 확산시켰는데
란다우는 빅 O 표기법을 "란다우 표기법(Landau notation)"이라고도 불리었고, 컴퓨터 과학에서 알고리즘의 복잡도를 계산하기 위해
단순하지만 강력한 도구로 사용되었다.
이외에도 빅 O 표기법은 하한을 표현하는 빅 오메가, 상한과 하한을 동시에 표현하는 빅 세타등으로 변형되기도 했다.
(워싱턴대학 CSE 373 슬라이드)
함수 $f(n)$과 $g(n)$이 있을 때, $f(n) = O(g(n))$은 충분히 큰 $n$에 대해
$ |f(n)| ≤ C · |g(n)|$
을 만족하는 양의 상수 $C$가 존재함을 의미한다.
즉, $f(n)$은 $g(n)$의 상수 배로 상한(upper bound)이 정해질 수 있다는 뜻이다.
예시를 하나 들어보자.
f(n) = 3n² + 2n + 1
일 때, $f(n)$은 $O(n^2)$이다. 최고차항인 $n^2$만 고려하고, 상수 계수는 무시하기 때문이다.
그렇다면 $f(n) = 2n + 10$일 때는?
이 경우 $f(n) = O(n)$이다.
빅 O 표기법은 함수의 점근적 성장률(asymptotic growth rate)을 표현하는 도구다.
한 문장으로 요약하면, 입력 크기가 커질수록 알고리즘의 복잡도가 어떻게 증가하는지를 나타낸다.
Big-O를 이용해 보통 두 가지 복잡도를 분석한다.
시간 복잡도(Time Complexity)
- 입력 크기에 따라서 알고리즘이 수행되는데 걸리는 '시간(연산횟수)'의 증가율을 나타낸다.
대표적인 Big O 시간 복잡도
O(1) → 상수 시간 (Constant Time)
예시:
배열에서 인덱스로 요소 접근 (예: arr[2]).
해시 테이블에서 키를 이용한 값 조회 (충돌 없는 경우).
설명: 입력 크기(n)와 무관하게 연산이 한 단계로 완료됨
O(log n) → 로그 시간 (Logarithmic Time)
예시: 이진 탐색으로 정렬된 배열에서 값 찾기.
균형 이진 탐색 트리(BST)에서 노드 검색.
설명: 입력 크기가 커질 때마다 연산 범위가 절반으로 줄어듬 (예: 데이터를 계속 분할하며 탐색).
O(n) → 선형 시간 (Linear Time)
예시: 배열의 모든 요소를 한 번씩 순회하는 반복문.
연결 리스트(Linked List)에서 특정 값 탐색.
설명: 입력 크기(n)에 정비례해 연산 시간이 증가
O(n log n) → 로그-선형 시간 (Linearithmic Time)
예시: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort).
대부분의 효율적인 비교 기반 정렬 알고리즘.
설명: 분할 정복(Divide and Conquer) 전략을 사용하며, n개의 요소를 반복적으로 절반으로 나누고(log n), 병합(n)
O(n²) → 이차 시간 (Quadratic Time)
예시: 중첩 반복문으로 배열의 모든 조합 확인 (예, 버블 정렬, 선택 정렬).
그래프에서 모든 노드 쌍의 최단 경로 계산 (플로이드-워셜 알고리즘).
설명: 입력 크기가 커질수록 연산 시간이 제곱으로 폭발적 증가.
O(2ⁿ) → 지수 시간 (Exponential Time)
예시: 피보나치 수열의 나이브 재귀 구현 (중복 계산 많음).
모든 가능한 부분집합(Subset) 생성.
설명: 입력 크기가 작아도 연산 시간이 기하급수적으로 증가하여 실용적이지 않다.
공간 복잡도(Space Complexity)
-입력 크기에 따라 알고리즘이 사용하는 메모리 양의 증가율을 나타낸다.
대표적인 Big O 공간 복잡도
O(1) → 상수 공간 (Constant Space)
예시: 단일 변수 사용 (예: 반복문의 인덱스 i).
입력 크기와 무관한 고정된 크기의 변수 (e.g., int a = 10).
설명: 입력 크기(n)와 관계없이 고정된 메모리만 사용
O(log n) → 로그 공간 (Logarithmic Space)
예시:균형 이진 탐색 트리(BST)의 재귀적 순회 (재귀 호출 스택 깊이).
퀵 정렬의 평균 공간 복잡도 (분할 정복 시 스택 깊이).
설명: 재귀 또는 분할 정복 알고리즘에서 스택/메모리 사용량이 입력 크기의 로그에 비례.
O(n) → 선형 공간 (Linear Space)
예시: 입력 배열을 복사해 저장 (예: newArr = arr.slice()).
그래프의 인접 리스트 표현 (노드 수에 비례한 메모리).
설명:입력 크기(n)에 정비례해 메모리 사용량이 증가
O(n log n) → 로그-선형 공간 (Linearithmic Space)
예시:병합 정렬(Merge Sort)의 최악 공간 복잡도 (임시 배열 사용).
특정 분할 정복 알고리즘의 재귀적 구현 (단계별 추가 메모리).
설명:재귀 호출 단계마다 선형 공간을 사용하고, 재귀 깊이가 로그인 경우 발생
O(n²) → 이차 공간 (Quadratic Space)
예시:그래프의 인접 행렬 표현 (n x n 행렬).
동적 계획법(DP)**의 2차원 테이블 (예: 최장 공통 부분 수열).
설명:입력 크기의 제곱에 비례해 메모리가 증가하며, 대규모 데이터에 비효율적
O(2ⁿ) → 지수 공간 (Exponential Space)
예시: 모든 부분집합(Subset) 저장 (예: n개 요소의 모든 조합).
재귀적 피보나치의 최악 공간 복잡도 (중복 호출 스택²).
설명:입력 크기가 작아도 메모리 사용량이 기하급수적으로 증가
둘 다 빅 오 표기법으로 표현되며, Big-O는 상한(upper bound)을 표현하는 표기이지만, 자주 Worst Case 분석과 함께 사용되는 경우가 많다.
차이점이 있다면
-시간 복잡도는 속도에 초점을 두고, 공간 복잡도는 메모리 사용량에 초점을 둔다.
트레이드 오프(trade-off)
-빠른 알고리즘은 메모리를 더 많이 써서(동적 계획법),
시간을 절약하거나, 메모리를 절약하여 시간이 더 걸리게 할 수 있다.
재귀함수와 반복문을 비교해보자, 시간 복잡도는 같을 수 있지만, 공간 복잡도는 재귀 함수(스택 메모리 사용)가 더 높을 수 있다.
가령 메모리를 더 사용해서 시간 복잡도를 낮추는 것중에 해시 테이블도 예시로 들 수 있다.
어쨌건 흔히 알려져있는 알고리즘에 대해서
필자가 Big-O를 표로 정리한 것을 보자.
시간 복잡도(최고-평균-최악)
알고리즘 | 최고 (BEST) | 평균 (AVERAGE) | 최악 (WORST) |
|---|---|---|---|
삽입 정렬 (Insertion Sort) | $O(n)$ | $O(n²)$ | $O(n²)$ |
선택 정렬 (Selection Sort) | $O(n²)$ | $O(n²)$ | $O(n²)$ |
버블 정렬 (Bubble Sort) | $O(n)$ | $O(n²)$ | $O(n²)$ |
병합 정렬 (Merge Sort) | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ |
퀵 정렬 (Quick Sort) | $O(n log n)$ | $O(n log n)$ | $O(n²)$ |
힙 정렬 (Heap Sort) | $O(n log n)$ | $O(n log n)$ | $O(n log n)$ |
셸 정렬 (Shell Sort) | $O(n log n)$ | $O(n^{1.3})$ | $O(n²)$ |
계수 정렬 (Counting Sort) | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ |
기수 정렬 (Radix Sort) | $O(nk)$ | $O(nk)$ | $O(nk)$ |
버킷 정렬 (Bucket Sort) | $O(n + k)$ | $O(n + k)$ | $O(n²)$ |
1. 삽입 정렬 (Insertion Sort)
최고(Best):
$O(n)$
이미 정렬된 데이터일 때, 각 요소를 비교하면서도 자리 이동이 필요 없음.
예: [1, 2, 3, 4]는 비교만 하고 삽입하지 않아도 됨.
평균(Average):
$O(n²)$
데이터가 랜덤하게 분포되어 있을 경우, 매 요소마다 평균 절반 정도의 자리 이동이 필요.
최악(Worst):
$O(n²)$
역순으로 정렬된 데이터일 때, 매 요소마다 모든 앞 요소와 비교 및 자리 이동이 필요.
예: [4, 3, 2, 1]에서는 각 요소마다 최대 n번의 비교와 이동이 필요.
2. 선택 정렬 (Selection Sort)
최고/평균/최악:
모두 $O(n²)$
입력 데이터 상태에 관계없이 항상 같은 성능을 보임.
이유: 매 단계마다 남은 배열에서 최솟값(또는 최댓값)을 찾아야 하므로, 비교 횟수는 항상 고정됨.
최고의 경우에도 교환 횟수가 줄어들 뿐, 비교 횟수는 변하지 않음.
3. 버블 정렬 (Bubble Sort)
최고(Best):
$O(n)$
이미 정렬된 데이터일 때, 한 번의 스캔으로 교환이 일어나지 않으면 조기 종료 가능.
예: [1, 2, 3, 4]에서는 교환이 없으므로 한 번의 전체 스캔 후 종료.
평균(Average):
$O(n²)$
랜덤한 데이터에서는 각 요소가 평균 절반 정도의 위치까지 이동해야 함.
최악(Worst):
$O(n²)$
역순으로 정렬된 데이터일 때, 매 요소마다 최대 n번의 비교와 교환이 필요.
예: [4, 3, 2, 1]에서는 모든 요소가 한 칸씩 이동해야 함.
4. 병합 정렬 (Merge Sort)
최고/평균/최악:
모두 $O(n log n)$
이유: 병합 정렬은 분할(Divide)과 결합(Conquer) 과정에서 항상 동일한 작업을 수행함.
입력 데이터 상태에 관계없이 분할과 병합 과정은 동일하게 진행됨.
5. 퀵 정렬 (Quick Sort)
최고(Best):
$O(n log n)$
피벗(Pivot)이 항상 중간값으로 선택될 때, 균형 잡힌 분할이 이루어짐.
예: [4, 1, 3, 2, 6, 5]에서 피벗이 중간값일 경우.
평균(Average):
$O(n log n)$
대부분의 경우 피벗이 균형 잡힌 위치로 선택되면 O(n log n) 성능을 유지.
최악(Worst):
$O(n²)$
피벗이 항상 가장 작은 값 또는 가장 큰 값으로 선택될 때, 불균형한 분할이 이루어짐.
예: [1, 2, 3, 4, 5]처럼 이미 정렬된 데이터에서 첫 번째 요소를 피벗으로 선택하면 매번 한쪽만 분할됨.
6. 힙 정렬 (Heap Sort)
최고/평균/최악:
모두 $O(n log n)$
이유: 힙 자료구조를 사용하여 데이터를 추출하는 과정에서 항상 동일한 작업을 수행함.
입력 데이터 상태에 관계없이 힙 구성과 추출 과정은 동일하게 진행됨.
7. 셸 정렬 (Shell Sort)
최고(Best):
$O(n log n)$
간격(Gap)이 잘 설정되고 데이터가 거의 정렬된 상태일 때 효율적.
평균(Average):
$O(n^{1.3})$
일반적인 경우 간격이 점진적으로 줄어들며 데이터가 점차 정렬됨.
물론 셸 정렬의 시간 복잡도는 gap sequence에 따라 달라지고
$O(n log² n) ~ O(n²)$ 사이로 알려져 있지만, 일반적으로 $O(n^{1.3})$ 의 경험적 측정값이 쓰이기도 한다.
최악(Worst):
$O(n²)$
간격이 잘못 설정되거나 데이터가 역순으로 정렬된 경우 비효율적.
8. 계수 정렬 (Counting Sort)
최고/평균/최악:
모두 $O(n + k)$
이유: 데이터 범위(k)가 작을 때, 데이터를 직접 계산하여 정렬하므로 입력 데이터 상태에 관계없이 동일한 성능.
단, k가 클 경우 메모리 사용량이 증가함.
9. 기수 정렬 (Radix Sort)
최고/평균/최악:
모두 $O(nk)$
이유: 각 자리수별로 정렬하므로, 데이터 크기(n)와 자릿수(k)에 비례하여 동일한 작업을 수행함.
입력 데이터 상태에 관계없이 동일한 성능을 보임.
10. 버킷 정렬 (Bucket Sort)
최고(Best):
$O(n)$
데이터가 균등하게 분포되어 있고, 버킷 내부 정렬이 필요 없을 때.
평균(Average):
$O(n + k)$
데이터가 대체로 균등하게 분포되어 있지만, 버킷 내부에서 일부 정렬이 필요할 때.
최악(Worst):
$O(n²)$
데이터가 한 버킷에 집중되어 있을 때, 해당 버킷 내부에서 정렬 비용이 증가함.
공간 복잡도(최고-평균-최악)
알고리즘 | 최고 (BEST) | 평균 (AVERAGE) | 최악 (WORST) |
|---|---|---|---|
삽입 정렬 | $O(1)$ | $O(1)$ | $O(1)$ |
선택 정렬 | $O(1)$ | $O(1)$ | $O(1)$ |
버블 정렬 | $O(1)$ | $O(1)$ | $O(1)$ |
병합 정렬 | $O(n)$ | $O(n)$ | $O(n)$ |
퀵 정렬 | $O(log n)$ | $O(log n)$ | $O(n)$ |
힙 정렬 | $O(1)$ | $O(1)$ | $O(1)$ |
셸 정렬 | $O(1)$ | $O(1)$ | $O(1)$ |
계수 정렬 | $O(k)$ | $O(k)$ | $O(k)$ |
기수 정렬 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ |
버킷 정렬 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ |
1. 삽입 정렬, 선택 정렬, 버블 정렬, 힙 정렬, 쉘 정렬
모두 제자리(In-place) 정렬 알고리즘으로, 추가적인 메모리가 거의 필요하지 않는다.
공간 복잡도는 항상 $O(1)$
2. 병합 정렬
분할된 배열을 임시 저장하기 위해 추가적인 배열이 필요합
공간 복잡도는 항상 $O(n)$이며, 이는 병합 정렬의 주요 단점 중 하나
3. 퀵 정렬
재귀 호출 스택으로 인해 추가 메모리가 필요합니다.
평균적으로 $O(logn)$의 공간이 필요하며, 최악의 경우 $O(n)$까지 증가할 수 있다.
4. 계수 정렬
데이터의 범위(k)에 따라 추가 메모리가 필요
공간 복잡도는 $O(k)$
5. 기수 정렬
각 자리수를 기준으로 정렬하므로 데이터 크기(n)와 범위(k)에 비례하는 추가 메모리가 필요
공간 복잡도는 $O(n+k)$
6. 버킷 정렬
데이터를 버킷으로 나누어 저장하므로 데이터 크기와 버킷 개수에 비례하는 추가 메모리가 필요(버킷 자체를 저장하는 데 필요한 공간은 $O(n + k)$이며,
데이터가 한 버킷에 몰리는 경우는 시간 복잡도에 영향을 준다.)
공간 복잡도는 $O(n+k)$
어쨌건 이 글은 정렬 알고리즘들의 Big O를 수학적으로 정리하는 그런 글이 아니다.
그럼 왜 이 글을 썼을까?
그건 Big-O의 한계를 말하기 위해서다.
모든 모델은 틀리지만, 어떤 것은 유용하다 -George Edward Pelham Box, 수학자
Big-O의 오해와 한계
Big-O는 복잡도를 단순화한 모델일 뿐, 현실의 모든 변수를 담을 수 없다.
단지 알고리즘의 효율성을 빠르게 비교하는 것일뿐이다.
그럼 예시를 들어보자
1. Big-O는 점근적 상한(Upper Bound)이다. Worst Case가 전부가 아니다.
using System;
using System.Diagnostics;
class QuickSortExample
{
// 최악의 경우: 첫 번째 요소를 피벗으로 선택
static void QuickSortWorst(int[] arr, int left, int right)
{
if (left >= right) return;
int pivot = arr[left];
int i = left + 1;
for (int j = left + 1; j <= right; j++)
{
if (arr[j] < pivot)
{
Swap(arr, i, j);
i++;
}
}
Swap(arr, left, i - 1);
QuickSortWorst(arr, left, i - 2);
QuickSortWorst(arr, i, right);
}
// 평균적인 경우: 중간 요소를 피벗으로 선택
static void QuickSortAvg(int[] arr, int left, int right)
{
if (left >= right) return;
int mid = left + (right - left) / 2;
Swap(arr, mid, right);
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
int pivotIndex = i + 1;
QuickSortAvg(arr, left, pivotIndex - 1);
QuickSortAvg(arr, pivotIndex + 1, right);
}
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int[] MakeSorted(int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i;
return arr;
}
static int[] MakeRandom(int n)
{
int[] arr = new int[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) arr[i] = rand.Next(n);
return arr;
}
static void Main()
{
const int N = 50000;
// JIT 웜업
int[] warmup = MakeRandom(1000);
QuickSortWorst(warmup, 0, warmup.Length - 1);
warmup = MakeRandom(1000);
QuickSortAvg(warmup, 0, warmup.Length - 1);
int[] sorted = MakeSorted(N);
var stopwatch = Stopwatch.StartNew();
QuickSortWorst(sorted, 0, sorted.Length - 1);
stopwatch.Stop();
Console.WriteLine($"최악의 경우 (n={N}, 정렬된 배열 + 첫 요소 피벗): {stopwatch.Elapsed.TotalMilliseconds:F2}ms");
int[] random = MakeRandom(N);
stopwatch.Restart();
QuickSortAvg(random, 0, random.Length - 1);
stopwatch.Stop();
Console.WriteLine($"평균적인 경우 (n={N}, 랜덤 배열 + 중간 요소 피벗): {stopwatch.Elapsed.TotalMilliseconds:F2}ms");
}
}퀵 정렬은 평균적으로 $O(n log n)$이지만, Worst Case는 $O(n²)$다. 관행적으로 Big O를 Worst Case 기준으로 쓸 때가 많다 보니, 퀵 정렬은 $O(n²)$알고리즘으로 소개되기도 하지만, 이론적 분류는 $O(n log n)$이다.
여기서 이론과 현실의 괴리가 생긴다. 위 코드를 실행해보면, 랜덤 배열(평균적 입력)에서 퀵 정렬은 실제로 $O(n log n)$에 가깝게 동작한다. $O(n²)$라는 표기만 보고 느린 알고리즘이라고 단정할 수 없다는 것이다.
더 나아가, 작은 n에서는 이론상 $O(n²)$인 알고리즘이 $O(n log n)$보다 빠른 경우도 있다. 캐시 지역성(cache locality) 때문이다. Big O는 상수 계수와 캐시 효율을 무시하므로, n이 충분히 크지 않으면 복잡도 등급보다 하드웨어 특성이 성능을 지배한다.
2. 상수 계수(Constant Factor)를 무시한다.
using System;
using System.Diagnostics;
class ConstantCoefficientExample
{
static long F(int n)
{
return 100L * n + 1000; // O(n)
}
static long G(int n)
{
return (long)(0.1 * n * n); // O(n²)
}
static void Main()
{
const int N = 10;
const int ITERATIONS = 10_000_000;
// JIT 웜업
F(N);
G(N);
long dummy = 0;
var stopwatch = Stopwatch.StartNew();
for (int i = 0; i < ITERATIONS; i++) dummy += F(N);
stopwatch.Stop();
Console.WriteLine($"O(n) 함수 {ITERATIONS:N0}회 반복: {stopwatch.Elapsed.TotalMilliseconds:F2}ms (dummy={dummy})");
dummy = 0;
stopwatch.Restart();
for (int i = 0; i < ITERATIONS; i++) dummy += G(N);
stopwatch.Stop();
Console.WriteLine($"O(n²) 함수 {ITERATIONS:N0}회 반복: {stopwatch.Elapsed.TotalMilliseconds:F2}ms (dummy={dummy})");
Console.WriteLine($"\nn={N}에서는 상수 계수 100이 붙은 O(n)이 O(n²)보다 느릴 수 있다.");
}
}$f(n) = 100n + 1000$과 $g(n) = 0.1n²$이 있다면, Big O는 각각 $O(n)$과 $O(n²)$로 분류한다.
그러나 n이 작을 때는 $g(n)$이 더 빠를 수 있다.
위 코드가 그 사례다. $n = 10$이면 상수 계수 100이 붙은 $O(n)$이 오히려 $O(n²)$보다 느리게 동작한다.
3. 동일한 복잡도라도 실제 성능은 다르다.
using System;
using System.Diagnostics;
class QuickSortExample
{
static void QuickSort(int[] arr, int left, int right)
{
if (left >= right) return;
int mid = left + (right - left) / 2;
Swap(arr, mid, right);
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
int pivotIndex = i + 1;
QuickSort(arr, left, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, right);
}
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void Main()
{
const int N = 1_000_000;
Random rand = new Random(42);
int[] baseArr = new int[N];
for (int i = 0; i < N; i++) baseArr[i] = rand.Next(N);
// JIT 웜업
int[] warmup = new int[1000];
Array.Copy(baseArr, warmup, 1000);
QuickSort(warmup, 0, warmup.Length - 1);
int[] arr = new int[N];
Array.Copy(baseArr, arr, N);
var stopwatch = Stopwatch.StartNew();
QuickSort(arr, 0, arr.Length - 1);
stopwatch.Stop();
Console.WriteLine($"퀵 정렬 (n={N:N0}): {stopwatch.Elapsed.TotalMilliseconds:F2}ms");
}
}using System;
using System.Diagnostics;
class HeapSortExample
{
static void HeapSort(int[] arr)
{
int n = arr.Length;
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
for (int i = n - 1; i > 0; i--)
{
Swap(arr, 0, i);
Heapify(arr, i, 0);
}
}
static void Heapify(int[] arr, int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] > arr[largest]) largest = right;
if (largest != i)
{
Swap(arr, i, largest);
Heapify(arr, n, largest);
}
}
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void Main()
{
const int N = 1_000_000;
Random rand = new Random(42);
int[] baseArr = new int[N];
for (int i = 0; i < N; i++) baseArr[i] = rand.Next(N);
// JIT 웜업
int[] warmup = new int[1000];
Array.Copy(baseArr, warmup, 1000);
HeapSort(warmup);
int[] arr = new int[N];
Array.Copy(baseArr, arr, N);
var stopwatch = Stopwatch.StartNew();
HeapSort(arr);
stopwatch.Stop();
Console.WriteLine($"힙 정렬 (n={N:N0}): {stopwatch.Elapsed.TotalMilliseconds:F2}ms");
}
}퀵 정렬과 힙 정렬은 평균 시간 복잡도가 모두 O(n log n)으로 동일하다.
그러나 힙 정렬은 상수 계수가 크고 메모리 접근 패턴이 불규칙해 캐시 효율성이 낮다. 위 두 코드를 실행해보면 이론적 복잡도는 같지만 실측 시간은 퀵 정렬이 대체로 빠르다.
이는 Big-O가 무시하는 요소들, 즉 상수 계수, 캐시 지역성(cache locality), 하드웨어 특성이 실제 성능을 결정하기 때문이다. 이전 글에서 다룬 이중 반복문의 row-major vs column-major 접근도 같은 맥락이다.
복잡도는 동일하지만 캐시 미스 증가로 속도 차이가 발생한다.
(눈으로 볼 수 있는 Big-O 시간 복잡도)
마치며...
결국 Big-O는 강력한 도구지만, 항상 정답은 아니다.
우리는 강력한 이론이 모든 것을 해결해줄 것처럼 이론을 숭배하는 경향이 있다.
하지만 이론은 현실에서 추출해낸 일부일 뿐이다.
이론을 문제 해결의 나침반으로 삼되, 그 길이 실제로 맞는지 주변도 살펴볼 필요가 있다.