알고리즘의 시간 복잡도와 공간 복잡도에 대한 설명
완전히 똑같은 작업을 수행하는 두 프로그램을 상상해 보세요. 각각에 천 개의 레코드를 입력하면 두 프로그램이 어떻게 다른지 구별할 수 없습니다. 하지만 십억 개의 레코드를 입력하면, 하나는 엔터 키에서 손을 떼기도 전에 작업을 끝내는 반면, 다른 하나는 다음 주 화요일까지도 작업을 계속할 것입니다.
같은 노트북, 같은 데이터입니다. 둘을 구분하는 것은 시간 복잡도인데, 이는 알고리즘에 입력값을 더 많이 줄수록 알고리즘의 작업량이 얼마나 빠르게 증가하는지를 나타내는 용어입니다.
이 글에서는 '빅 O'라는 용어가 실제로 무엇을 의미하는지, 빅 O 표기법으로 어떻게 표현하는지, 실제 코드에서 어떻게 계산하는지, 그리고 공간 복잡도가 어떻게 작용하는지 살펴보겠습니다. 마지막으로, 이 모든 것이 단순한 숙제가 아니라 실제 비용이 드는 영역, 바로 스마트 계약에 대해 알아보겠습니다.
알고리즘의 시간 복잡도란 무엇인가요?
잠시 초 단위는 잊어버리세요. 시간 복잡도는 단계 수를 세는 것입니다. 비교, 할당, 그리고 약간의 산술 연산 등을 거치면 전체 과정을 입력 크기인 n의 함수로 나타낼 수 있습니다.
상상할 수 있는 가장 지루한 기능입니다:
Python def print_all(items): for item in items: print(item)
물품 10개? 10번 왕복. 1만 개? 1만 번 왕복.
작업량은 입력값 옆에서 직선으로 증가하므로 이를 O(n)이라고 부릅니다.
자, 어쩌면 각 여정마다 실제로는 한 번의 수술이 아니라 세 번의 수술이 필요할지도 모릅니다. 좋습니다, 그럼 3n이라고 하죠. 솔직히 아무도 신경 쓰지 않습니다. 왜냐하면 목록을 두 배로 늘리면 작업량도 두 배가 되고, 바로 그 증가 곡선이 우리가 원하는 것이기 때문입니다. 정확한 숫자는 일부러 무시하는 겁니다.
그래서 모든 DSA 강의와 코딩 면접의 절반이 시간 복잡도를 강조하는 것입니다. 알고리즘의 복잡도를 한눈에 파악할 수 있다면, 테스트조차 해보지 않은 입력 데이터에 대해 알고리즘이 어떻게 동작할지 예측할 수 있습니다. 실제 운영 환경에서는 대부분의 데이터가 그런 입력 데이터에 해당합니다.
알고리즘 성능을 측정하는 데 실행 시간이 부적절한 이유
그렇다면 타이머를 사용해서 실행하면 되지 않을까요? 많은 사람들이 그렇게 하고 있고, 저도 그 이유를 이해합니다. 하지만 문제는 실행 시간이 알고리즘과는 전혀 상관없는 여러 가지 요소 때문에 길어진다는 것입니다.
- 하드웨어. 제 5년 된 노트북과 최신 클라우드 박스는 같은 스크립트를 실행해도 전혀 다른 결과를 보여줄 수 있습니다.
- 프로그래밍 언어. 동일한 반복문을 C 언어와 파이썬으로 작성해 보면 10배 이상의 차이가 날 수 있습니다.
- 시스템 부하. 백그라운드 업데이트 프로그램이 실행되고, 가비지 컬렉터가 작동하고, 캐시가 초기화됩니다. 따라서 검색 결과가 변동될 수 있습니다.
- 입력값이 무엇이든 간에, 거의 정렬된 데이터에서는 빠른 정렬 속도가 섞인 데이터에서는 매우 느려질 수 있습니다.
스톱워치는 한 번의 실험과 한 번의 입력값만 측정할 수 있습니다. 100배에 달하는 데이터를 입력하면 아무런 결과도 얻을 수 없습니다.
단계 수는 변동하지 않습니다. 동일한 알고리즘, 동일한 입력값을 사용하면 랙 서버에서 실행되는 Rust든 누군가의 스마트폰에서 실행되는 JavaScript든 단계 수는 동일합니다. 이것이 바로 벤치마킹을 하기 전에 두 솔루션 간의 시간 복잡도를 비교하는 것이 공정한 이유입니다. 물론 벤치마킹 후에도 성능 향상을 위해 벤치마킹을 진행하는 것이 좋습니다. 다만, 그 결과는 다른 차원의 문제가 될 뿐입니다.
빅 O 표기법 및 기타 점근 표기법 설명
교과서에서는 이를 점근 표기법이라고 부르는데, 이름만 들으면 어려워 보이지만 실제로는 간단합니다. n이 엄청나게 커지도록 하고 작은 요소들은 더 이상 고려하지 않기 때문에 상수 곱셈과 아주 작은 입력값들은 사라지고 성장 곡선만 남게 됩니다. 알아두면 유용한 점근 곡선은 세 가지가 있습니다.
| 표기법 | 설명 내용 | 쉬운 의미 | 예 |
|---|---|---|---|
| 빅 O, O(f(n)) | 상한 | 알고리즘의 성장률은 f(n)보다 빠르지 않습니다. | 선형 검색은 O(n)입니다. |
| 빅오메가, Ω(f(n)) | 하한 | 이 알고리즘은 최소한 f(n)개의 작업이 필요합니다. | 모든 비교 정렬은 Ω(n log n)입니다. |
| 빅-세타, Θ(f(n)) | 꽉 묶인 | 상한과 하한이 일치합니다 | 병합 정렬은 Θ(n log n)입니다. |
실제로 빅 O 표기법은 거의 95%의 경우에 사용됩니다. 이는 실행 시간의 상한을 설정하는데, 괄호 안의 증가율보다 실행 시간이 더 빨리 증가하지 않는다는 것을 의미합니다. 제가 처음으로 실제 직장에서 코드 리뷰를 했을 때, 한 선임 개발자가 중첩 루프 옆에 "O(n²), 수정해 주세요"라고 썼는데, 그 의미는 최악의 경우 시간 복잡도가 n²이고 리스트가 앞으로 훨씬 더 길어질 것이라는 뜻이었습니다.
오메가와 세타는 주로 알고리즘 분석 관련 대학 강의에서나 볼 수 있는 표기법이고, 저는 직장에서 이 두 표기법을 써본 지 몇 년은 된 것 같습니다. 빅 O 표기법이 더 많이 쓰이는 이유는 회의에서 사람들이 실제로 묻는 질문, 즉 "교통량이 세 배로 늘어나면 상황이 얼마나 심각해질까요?"라는 질문에 대한 답을 제시하기 때문입니다.
한 가지 기술적인 점이 저를 한동안 헷갈리게 했습니다. 빅 O 표기법은 상한선일 뿐이므로, 엄밀히 말하면 O(n) 함수는 O(n²) 함수이기도 합니다. 마치 키 152cm(5피트)인 사람을 "213cm(7피트) 미만"이라고 하는 것과 같습니다. 맞는 말이지만, 사실상 쓸모없는 말이죠. 누구나 자신이 정당화할 수 있는 가장 엄격한 상한선을 제시하니까 저도 그렇게 하겠습니다.
일반적인 시간 복잡도 클래스와 예시
실제 코드에서 보게 될 클래스는 그리 많지 않습니다. 복잡한 클래스까지 포함해도 아마 7개 정도일 겁니다. n=1,000일 때 각 클래스의 대략적인 비용은 다음과 같습니다.
| 수업 | 이름 | 전형적인 예 | n = 1,000에서의 연산 |
|---|---|---|---|
| O(1) | 끊임없는 | 배열 인덱스, 해시 테이블 조회 | 1 |
| O(log n) | 로그 | 이진 검색 | ~10 |
| 에) | 선의 | 목록 스캔 | 1,000 |
| O(n log n) | 선형적 | 병합 정렬, 퀵 정렬(평균) | 약 10,000 |
| O(n²) | 이차식 | 중첩 루프, 버블 정렬 | 1,000,000 |
| O(2ⁿ) | 지수적 | 단순 재귀 피보나치 | 우주에 있는 원자보다 더 많은 것 |
| 에!) | 계승 | 무식한 여행 판매원 | 훨씬 더 큰 |
O(1): 상수 시간
Python 딕셔너리에 키가 10개 있든 1천만 개 있든, 키로 하나를 가져오는 데 드는 비용은 거의 동일하며, 목록에서 항목을 읽는 데 드는 비용도 마찬가지입니다.[5] 이러한 평탄성이 상수 시간의 핵심입니다.
O(log n): 로그 시간
저는 이런 알고리즘들을 "1에서 100 사이의 숫자를 추측하는" 알고리즘이라고 생각합니다. 즉, 추측할 때마다 남은 숫자의 절반이 제외되는 방식이죠. 이진 탐색은 정렬된 리스트에서 정확히 그런 방식으로 작동합니다.
Python 함수 `def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1`
10억 개의 항목을 정렬하려면 약 30번의 비교만 필요하지만, 하나씩 일일이 비교하려면 10억 번 모두 비교해야 할 수도 있다는 점이 여전히 재밌게 느껴집니다.
O(n) 및 O(n log n)
선형 알고리즘은 마치 스프레드시트 열에서 가장 큰 숫자를 눈으로 찾는 것처럼 각 요소를 고정된 횟수만큼 방문합니다. O(n log n)은 괜찮은 정렬 알고리즘의 시간 복잡도를 나타냅니다. 병합 정렬은 리스트를 개별 항목으로 분할(log n 단계 분할)한 다음, 각 단계마다 선형적인 과정을 한 번씩 수행하면서 병합합니다. 따라서 데이터가 정렬된 상태로 들어오든 뒤섞인 상태로 들어오든 실행 시간은 일정합니다.
O(n²) 및 그보다 더 나쁨
2차 함수 코드는 거의 항상 루프 안에 또 다른 루프가 숨겨져 있는 구조를 가지고 있습니다. 예를 들어, 모든 쌍을 비교하는 중복 검사 코드가 그렇습니다.
Python 함수 `has_duplicate(items)` 함수는 다음과 같이 정의됩니다. `for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
지수적 증가와 팩토리얼 증가는 훨씬 더 비효율적입니다. 교과서적인 재귀적 피보나치 수열은 같은 하위 문제를 계속해서 반복적으로 풀기 때문에 n이 1씩 증가할 때마다 작업량이 대략 두 배로 늘어납니다. n=20일 때는 알아차리지 못하겠지만, n=60이 되면 저녁을 요리하고, 먹고, 설거지를 해도 작업이 끝나지 않을 것입니다.
시간 복잡도를 단계별로 계산하는 방법
시간 복잡도를 계산하는 데 형식적인 증명이 필요한 경우는 거의 없습니다. 저는 이 목록을 머릿속으로 훑어보는데, 제가 접하는 대부분의 코드가 여기에 포함됩니다.
- n을 정의하세요. 입력 크기를 결정하세요. 예를 들어 리스트의 길이, 그래프의 노드 개수, 숫자의 자릿수 등이 있습니다.
- 각 줄의 작업량을 계산합니다. 간단한 문장(할당, 비교, 산술)은 O(1)의 비용이 듭니다.
- 연속적인 블록을 더합니다. n에 대해 각각 반복되는 두 개의 루프가 연속적으로 실행되면 n + n = 2n이 됩니다.
- 중첩된 블록을 곱합니다. n을 반복하는 루프 안에 또 다른 n을 반복하는 루프가 있으면 n × n = n²이 됩니다.
- 상수항을 생략합니다. 2n은 n이 되고, 500은 1이 됩니다.
- 지배적인 항만 남겨둡니다. n² + n에서 n이 커질수록 n² 항이 나머지 항보다 훨씬 커집니다.
간단하네요. 계산식은 T(n) = 3n² + 5n + 2입니다. 100만(million)을 대입해 보세요. 3n²은 3조이고, 5n은 500만입니다. 반올림 오차입니다. 계산식을 O(n²)으로 하면 됩니다.
한 단계씩 건너뛰는 대신 빙빙 도는 루프는 더 교묘합니다.
Python 함수 `count_halvings(n)`: `steps = 0` `while n > 1: n //= 2` `steps += 1` `return steps`
매 단계마다 n이 절반으로 줄어들기 때문에 이 while 루프는 대략 log₂(n)번 반복 후에 종료됩니다. 이것이 바로 "시간 복잡도가 O(log n)인 경우는 언제인가?"라는 질문에 대한 답입니다. 남은 값이 매 단계마다 상수만큼 줄어든다면, 시간 복잡도가 O(log n)이 되는 것입니다.
재귀에는 점화식이라는 도구가 하나 더 필요합니다. 병합 정렬은 두 번의 절반 크기 작업을 수행한 다음 병합을 수행하므로 T(n) = 2T(n/2) + n입니다. 마스터 정리는 이러한 형태의 점화식을 위한 요약본이며, 이 경우 O(n log n)의 시간 복잡도를 제공합니다.
경쟁 프로그래밍에서 자주 사용하는 경험 법칙이 하나 있는데, 일반적인 컴퓨터는 초당 약 10⁸개의 단순 연산을 처리합니다. 아주 대략적인 수치지만, 제출 버튼을 누르기 전에 솔루션의 시간 복잡도를 검증하기에는 충분합니다. n이 10⁵일 때, O(n²)은 약 10¹⁰개의 연산이므로 시간 초과가 발생합니다. O(n log n)은 200만 미만이므로 문제없이 실행됩니다.
최악의 경우, 최상의 경우 및 평균적인 경우 분석
같은 알고리즘에 다른 입력을 넣으면 작업량이 크게 달라질 수 있습니다. 선형 검색이 이를 잘 보여줍니다.
- 최상의 경우: 원하는 제품이 바로 맨 앞에 있는 거죠. 한 번의 비교로 바로 구매할 수 있어요.
- 최악의 경우: 맨 마지막에 있거나 아예 없을 수도 있습니다. 그러면 비교 횟수가 n번이 됩니다.
- 평균적인 경우: 만약 어느 곳이든 동일한 확률로 발생할 수 있다면, 평균적으로 n/2 정도를 확인하게 될 것입니다. 하지만 여전히 O(n)입니다.
개발자에게 어떤 것의 "복잡성"에 대해 물어보면 거의 항상 최악의 경우 시간 복잡도를 알려줄 것입니다. 왜냐하면 그 수치는 계획을 세울 때 참고할 수 있는 확실한 값이기 때문입니다.
API가 최악의 경우 O(n)의 시간 복잡도로 요청을 처리한다고 가정해 봅시다. 좋습니다. 이제 가장 느린 요청이 어떻게 동작하는지 알게 되었고, 누군가가 고의로 잘못된 데이터를 보내는 경우에도 대비할 수 있게 되었습니다. 실제로 공격자는 이런 짓을 자주 합니다. 해시 테이블 충돌을 일으키는 키를 알아내면, 한동안은 그 키들만 보게 될 것입니다.
최악의 시나리오가 거의 발생하지 않을 때는 평균적인 경우를 살펴보는 것이 좋습니다. 퀵소트가 대표적인 예인데, 평균 시간 복잡도는 O(n log n)이지만, 이미 정렬된 데이터에서 피벗을 임의로 선택하면 O(n²)까지 치솟습니다. 표준 라이브러리들은 무작위 피벗을 사용하거나 재귀 호출이 지나치게 깊어지면 다른 정렬 알고리즘으로 전환하는 방식으로 이 문제를 해결합니다.
공간 복잡성과 보조 공간이란 무엇인가요?
메모리는 알고리즘이 소모하는 또 다른 비용입니다. 공간 복잡도는 입력 크기가 커짐에 따라 필요한 메모리 양을 나타내며, 시간과 마찬가지로 빅 O 표기법을 사용합니다.
메모리의 일부는 입력 자체이며, 이는 사용 목적과 관계없이 비용이 발생합니다. 실제로 제어할 수 있는 부분은 보조 공간이라고 하는데, 여기에는 임시 변수나 새 배열처럼 코드가 실행되는 동안 할당하는 추가 공간과, 문제가 발생하기 전까지는 아무도 기억하지 못하는 호출 스택이 포함됩니다.
몇 가지 간단한 사례를 살펴보겠습니다.
- 두 변수를 교환하려면 다른 어떤 것과 상관없이 몇 개의 슬롯이 필요하므로 O(1) 보조 공간이 필요합니다.
- n개의 항목으로 이루어진 리스트를 새로운 리스트로 복사하는 데에는 O(n)의 추가 메모리가 필요합니다.
- n단계 깊이로 재귀 호출을 하면 스택에 n개의 프레임이 남게 되는데, 이는 배열을 생성하지 않았음에도 불구하고 O(n) 공간을 차지합니다.
저는 한 주니어 개발자가 마지막 문제 때문에 오후 내내 허비하는 것을 지켜봤습니다. 그 재귀 함수는 메모리를 전혀 사용하지 않는 것처럼 보였지만, 완료되지 않은 모든 호출이 스택에 쌓여 더 깊은 단계의 호출이 반환되기를 기다리고 있었고, 큰 입력값이 들어오면 스택 오버플로로 전체 프로그램이 멈춰버렸습니다.
최적화의 대부분은 메모리 사용량을 시간으로, 또는 그 반대로 바꾸는 것입니다. 메모이제이션은 이미 계산한 결과를 캐시하여 단순한 피보나치 수열 계산 시간을 O(2ⁿ)에서 O(n)으로 줄여주지만, 대신 O(n)의 메모리 사용량을 필요로 합니다. 해시 테이블은 버킷에 공간을 할당하는 대신 평균 조회 시간을 O(1)로 줄여줍니다. 64GB RAM을 탑재한 서버에서는 이러한 메모리 사용량 교환이 당연한 선택처럼 보이지만, 마이크로컨트롤러나 스마트 계약 내부에서는 신중하게 고려해야 합니다.
일반적인 데이터 구조의 시간 및 공간 복잡도
적절한 데이터 구조를 선택하는 것이 루프 내부의 세부적인 튜닝보다 훨씬 효과적일 때가 많습니다. 가장 자주 사용하게 될 데이터 구조들의 평균적인 비용은 다음과 같습니다.
| 데이터 구조 | 입장 | 찾다 | 끼워 넣다 | 삭제 | 공간 |
|---|---|---|---|---|---|
| 정렬 | O(1) | 에) | 에) | 에) | 에) |
| 연결 리스트 | 에) | 에) | O(1) | O(1) | 에) |
| 해시 테이블 | 해당 없음 | O(1) | O(1) | O(1) | 에) |
| 균형 이진 검색 트리 | O(log n) | O(log n) | O(log n) | O(log n) | 에) |
| 이진 힙 | 최소/최대값의 경우 O(1) | 에) | O(log n) | O(log n) | 에) |
두 가지 각주. 연결 리스트 삽입 및 삭제는 노드를 이미 보유하고 있는 경우에만 O(1)입니다. 그리고 해시 테이블은 많은 키가 충돌할 때 O(n)까지 떨어질 수 있습니다.
정렬 알고리즘 또한 매우 다양합니다.
| 정렬 알고리즘 | 최상의 | 평균 | 최악의 | 보조 공간 |
|---|---|---|---|---|
| 버블 정렬 | 에) | O(n²) | O(n²) | O(1) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | 에) |
| 퀵소트 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) |
병합 정렬은 예측 가능하지만 추가 메모리가 필요합니다. 힙 정렬은 제자리 정렬을 수행하며 최악의 경우에도 동일한 성능을 유지합니다. 퀵 정렬은 성능 상한선이 다소 떨어지지만 실제 사용에서는 더 나은 결과를 보이는 경향이 있습니다.
블록체인 및 스마트 계약의 시간 복잡도
여기서부터 흥미로워집니다. 자체 서버에서는 허술한 알고리즘이 CPU를 낭비하고 사용자를 짜증나게 하는 정도로 그칠 수 있습니다. 하지만 이더리움이나 다른 EVM 체인에서는 돈을 낭비하는 결과를 낳습니다. 스마트 계약이 실행하는 모든 오퍼레이션 코드(opcode)는 가스 비용을 발생시키며, 이 비용은 해당 체인의 네이티브 코인으로 지불됩니다. 따라서 실행 횟수는 누군가의 청구서에 항목으로 표시됩니다. 즉, 시간 복잡도가 나쁘면 비용이 발생한다는 뜻입니다.
토큰 보유자 한 명 한 명을 순회하며 보상을 지급하는 컨트랙트가 있다고 가정해 봅시다. 시간 복잡도는 O(n)이고, 새로운 보유자가 생길 때마다 가스 비용이 증가합니다. 출시 당일에는 아무도 이를 알아채지 못합니다.
그러면 보유자 목록은 계속 늘어납니다. 어느 날, 지급에 필요한 가스량이 블록 가스 한도(단일 블록에 포함될 수 있는 가스량의 상한선)를 초과하게 됩니다. 그러면 거래는 더 이상 진행될 수 없습니다. "느리다"는 문제가 아니라, 거래가 절대 성공하지 못하고, 해당 기능 뒤에 대기 중이던 자금은 사실상 묶이게 됩니다. 감사 기관에서는 이런 무한 루프를 서비스 거부 공격으로 간주하며, 이는 타당한 지적입니다.
해결책은 바로 복잡성 사고방식에 있습니다.
- 작업을 여러 번의 거래에 걸쳐 고정된 크기의 배치로 나눕니다.
- 반대로 하면 각 사용자가 자신의 보상을 받을 수 있습니다. 모든 호출은 O(1)입니다.
- 반복문을 머클 증명으로 바꾸세요.
온체인에서 log n이 왜 그렇게 중요한지 보여주는 예시로 머클 증명을 좋아합니다. 머클 트리는 방대한 양의 데이터를 하나의 루트 해시로 해싱합니다.
하나의 항목이 n개의 항목으로 이루어진 집합에 속한다는 것을 증명하려면 대략 log₂(n)개의 해시값이 필요합니다. 백만 개의 항목이 있다면 대략 20개 정도입니다. 백만 개가 아니라요. 에어드롭은 이러한 원리를 이용하고, 가벼운 비트코인 지갑은 전체 블록을 다운로드하지 않고도 거래를 확인하기 위해 같은 방식을 사용합니다.
오프체인에서도 마찬가지입니다. 모든 미결제 송장을 스캔하여 들어오는 모든 블록체인 거래를 송장과 대조하는 결제 백엔드를 상상해 보세요. 결제당 O(n)의 시간이 소요되며, 상점 규모가 커질수록 속도는 더욱 느려집니다. 송장을 주소 또는 ID를 키로 하는 해시맵에 저장하면 각 대조 작업은 O(1)의 시간 복잡도를 갖습니다. 그리고 이러한 시스템을 직접 구축하고 관리하는 것이 번거롭다면 Plisio 와 같은 암호화폐 결제 게이트웨이를 이용할 수 있습니다.
