🟣 어느 알고리즘이 더 빠른가
같은 문제를 푸는 코드가 두 개 있다고 하자. 어느 쪽이 더 빠른가. 가장 단순한 답은 둘 다 돌려 보고 시계로 재는 것이다. 그런데 이 방법은 믿기 어렵다. 내 노트북에서 잰 시간은 서버에서 다르고, 입력이 작을 땐 A가 빠르다가 입력이 커지면 B가 빠른 일이 흔하다. 컴파일러 최적화나 캐시 상태에 따라서도 흔들린다.
우리가 정말 알고 싶은 것은 특정 기계에서의 초 단위 시간이 아니다. 입력이 커질 때 연산량이 얼마나 빠르게 늘어나는가, 그 증가율이다. 입력 크기를 n이라 두고, n이 커질 때 알고리즘이 몇 번의 기본 연산을 하는지를 n의 함수로 나타낸다. 이렇게 하면 기계와 언어를 걷어내고 알고리즘 자체의 성질만 비교할 수 있다. 이 장은 그 자를 만드는 이야기다.
🟣 상수와 저차항을 버리는 이유
입력 크기 n짜리 배열을 한 번 훑는 코드가 있다고 하자. 반복문 안에서 대입 두 번, 비교 한 번을 한다면 연산 횟수는 대략 3n + 5 정도다. 여기서 우리는 과감하게 3n + 5를 그냥 n으로 본다. 상수 계수 3과 상수항 5를 버리는 것이다.
버려도 되는 이유는 목적이 증가율이기 때문이다. n이 100만이 되면 3n은 300만이고 +5는 무시할 수준이다. 계수 3도 기계가 두 배 빠르면 사라지는 수준의 차이다. 반면 n² 짜리 알고리즘은 n이 100만일 때 1조에 이른다. 저차항이나 상수로는 절대 메울 수 없는 격차가 최고차항에서 벌어진다. 그래서 최고차항만 남기고 나머지를 버린다.
이 버림을 형식으로 정한 것이 점근 표기법이다. 흔히 빅오 하나만 쓰지만 원래는 세 종류다.
O(f(n)): 상한. 아무리 나빠도 이 증가율을 넘지 않는다.Ω(f(n)): 하한. 아무리 좋아도 이보다는 느리다.Θ(f(n)): 상한과 하한이 같을 때. 증가율이 정확히f(n)이다.
엄밀히는 "어떤 상수 c와 충분히 큰 n에 대해 T(n) ≤ c·f(n)이면 T(n) = O(f(n))"으로 정의한다. 실무에서는 대개 빅오로 최악의 경우를 말하지만, 정렬 하한을 논할 때처럼 "이보다 빠를 수 없다"를 말하려면 Ω가 필요하다.
🟣 복잡도 계층: 눈에 익혀야 할 몇 가지
복잡도 분석이 몸에 배면 코드를 보자마자 대략의 등급이 보인다. 자주 나오는 계층을 증가율 순으로 익혀 두면 유용하다.
체감을 위해 n이 100만일 때를 떠올리면 좋다. O(log n)은 약 20번, O(n)은 100만 번, O(n log n)은 약 2천만 번이다. 여기까진 현대 컴퓨터가 순식간에 처리한다. 그런데 O(n²)은 1조 번이라 수십 초 단위로 넘어가고, O(2ⁿ)은 n이 고작 60만 돼도 우주의 나이를 넘긴다. 다항 시간(polynomial)과 지수 시간(exponential) 사이의 벽이 여기서 갈린다. 이 벽은 마지막 장의 NP 이야기에서 다시 만난다.
🟣 재귀의 비용은 점화식으로 잰다
반복문은 복잡도를 세기 쉽다. 문제는 자기 자신을 부르는 재귀 함수다. 함수 안에서 다시 함수를 부르니 연산 횟수가 한눈에 안 들어온다. 이럴 때 쓰는 도구가 점화식(recurrence)이다.
점화식은 크기 n 문제의 비용을 더 작은 문제의 비용으로 표현한 식이다. 예를 들어 배열을 반으로 나눠 각각 재귀로 풀고, 합치는 데 n에 비례하는 일을 하는 알고리즘이라면 이렇게 쓴다.
T(n) = 2·T(n/2) + O(n)
크기 n 문제 하나가 크기 n/2 문제 두 개와, 합치는 비용 O(n)으로 이뤄진다는 뜻이다. 이 식을 실제 증가율로 풀어내는 방법이 두 가지 있다.
🚀 재귀 트리로 펼치기
첫 번째는 재귀 트리다. 점화식을 실제로 한 겹씩 펼쳐, 각 단계에서 하는 일의 총량을 더한다. 위 점화식은 매 단계마다 문제가 절반으로 줄고 개수는 두 배가 된다. 그래서 각 단계에서 합치는 데 드는 비용의 합이 항상 O(n)으로 일정하다. 문제가 1이 될 때까지 단계 수는 log₂ n이므로, 전체는 O(n) × log n, 곧 O(n log n)이다.
🚀 마스터 정리로 바로 읽기
트리를 매번 펼치기는 번거롭다. T(n) = a·T(n/b) + f(n) 꼴, 즉 문제를 b분의 1 크기의 a개로 나누는 흔한 점화식은 마스터 정리로 답을 바로 읽을 수 있다. 핵심은 두 힘의 크기 비교다. 하나는 재귀가 쪼개면서 늘어나는 부분문제의 총량인 n^(log_b a)이고, 다른 하나는 매 단계에서 합치는 비용 f(n)이다.
- 부분문제 쪽이 크면(
f(n)이 더 작으면) 답은Θ(n^(log_b a)). 잎 노드의 일이 지배한다. - 둘이 비슷하면 로그가 한 겹 붙어
Θ(n^(log_b a) · log n). - 합치는 쪽이 크면(
f(n)이 더 크면) 답은Θ(f(n)). 뿌리의 일이 지배한다.
앞의 T(n) = 2T(n/2) + O(n)은 n^(log₂ 2) = n이고 합치는 비용도 n이라 둘째 경우다. 그래서 Θ(n log n)이 나온다. 마스터 정리를 처음 볼 땐 세 경우가 왜 이렇게 갈리는지 낯설었는데, 재귀 트리를 몇 번 손으로 펼쳐 보고 나서야 "결국 뿌리와 잎 중 어디가 일을 더 하느냐"라는 한 문장으로 정리됐다.
🟣 최악, 평균, 최선을 구분한다
같은 알고리즘이라도 입력에 따라 연산량이 다르다. 정렬된 배열에 이진 탐색을 하면 운 좋게 한가운데서 바로 찾을 수도 있고(최선 O(1)), 끝까지 좁혀 가며 찾을 수도 있다(최악 O(log n)). 그래서 복잡도는 셋으로 나눠 말한다.
실무와 면접에서 기본값은 최악의 경우다. "평소엔 빠른데 가끔 느리다"는 시스템은 그 가끔이 장애가 되기 때문이다. 다만 퀵 정렬처럼 최악은 O(n²)이지만 평균은 O(n log n)이고 그 평균이 현실에서 거의 항상 나오는 경우가 있다. 이때는 평균 분석과 랜덤화가 중요해지는데, 이 이야기는 다음 장 정렬에서 자세히 다룬다.
🟣 정리
- 알고리즘의 빠르기는 초 단위 시간이 아니라 입력이 커질 때의 증가율로 잰다. 기계와 언어를 걷어내고 알고리즘 자체를 비교하기 위해서다.
- 점근 표기법은 상수와 저차항을 버리고 최고차항만 남긴다.
O는 상한,Ω는 하한,Θ는 둘이 같을 때 쓴다. - 다항 시간과 지수 시간 사이에는 넘을 수 없는 벽이 있다.
O(n²)까지는 어떻게든 버티지만O(2ⁿ)은 작은 입력에서도 무너진다. - 재귀의 비용은 점화식으로 세운다. 재귀 트리로 펼치거나 마스터 정리로 바로 읽는다. 마스터 정리는 결국 뿌리와 잎 중 어디가 일을 더 하느냐를 비교하는 것이다.
- 복잡도는 최악·평균·최선으로 나뉘고, 기본값은 최악이다.
시간 복잡도는 코드 리뷰에서 "이 반복문 안의 조회가 사실 O(n)이라 전체가 O(n²)이 됩니다" 같은 지적으로 매일 쓰인다. 자를 손에 쥐었으니, 이제 이 자로 알고리즘들을 실제로 재 볼 차례다. 다음 장은 큰 문제를 반으로 쪼개는 분할정복과, 그 대표 사례인 정렬이다.