시간 복잡도는 입력 크기에 따른 알고리즘 작업량의 증가를 분석한다. 이 문서는 O·Ω·Θ, 최선·최악·기댓값·분할 상환 분석을 구분하고, 반복문·재귀·복사·해시·전처리 비용을 실제 연산 횟수 예제로 계산한다.
무엇을 측정하는 개념인가
시간 복잡도는 입력 크기에 따라 알고리즘의 작업량이 어떻게 증가하는지 표현하는 개념이다. “이 함수는 0.2초 걸린다”는 특정 실행의 측정과 다르다. 같은 알고리즘도 컴퓨터, 언어, 입력 내용에 따라 실제 시간이 달라지므로 기본 연산 수를 세는 모델로 증가율을 비교한다.
예를 들어 목록에서 없는 값을 찾으려면 선형 탐색은 모든 원소를 비교한다. 목록 길이가 두 배가 되면 비교 횟수도 두 배가 된다. 반면 정렬된 배열에서 후보 범위를 절반씩 줄이는 이진 탐색은 입력 길이가 두 배가 되어도 비교 횟수가 대략 한 단계 늘어난다. 이 차이는 큰 입력에서 선택의 기준이 된다.
복잡도는 함수 이름에 붙은 영구적인 성질이라기보다 명시한 알고리즘·구현·입력 크기·계산 모델에 대한 분석이다. 같은 코드처럼 보여도 배열 접근과 연결 리스트 탐색의 비용은 다르다. 기본 연산을 무엇으로 세었는지와 최악·평균 중 무엇을 분석했는지를 함께 말해야 한다.
이 문서의 Python 예제는 실행 시간을 임의의 숫자로 제시하는 대신 반복·비교·이동 횟수를 직접 세어 예측과 대조한다. 초 단위 벤치마크는 환경에 따라 달라지지만 작은 예제의 카운터는 분석한 식을 재현하기 쉽다. 카운터를 넣은 프로그램 자체에도 추가 비용이 있으므로 계측 결과를 원래 코드의 절대 속도로 해석하지 않는다.
입력 크기 n을 먼저 정의하기
n은 관습적인 이름일 뿐 항상 원소 수인 것은 아니다. 문자열 알고리즘에서는 문자열 길이, 그래프에서는 정점 수 V와 간선 수 E, 행렬에서는 행과 열의 수를 따로 사용할 수 있다. 입력 크기를 하나로 압축하면서 중요한 변수를 숨기면 분석이 부정확해진다.
정수 N을 입력받는 문제에서는 N의 값과 그 값을 표현하는 비트 수가 다르다. 양의 정수 N은 대략 log₂N개의 비트로 표현된다. N번 반복하는 알고리즘은 N의 값에는 선형이지만 입력 비트 수 b에 대해서는 대략 2^b에 비례할 수 있다. 숫자가 크다는 말과 입력이 길다는 말을 구분해야 한다.
아래 8,16,32는 값이 두 배씩 커지지만 bit_length는 4,5,6이다. 0의 표현과 부호, 파일 인코딩까지 포함한 실제 입력 형식은 별도 명세가 필요하다. 예제는 양의 정수의 크기 관계를 보여준다.
여러 입력이 있으면 n과 m을 분리해 O(n+m)이나 O(nm)으로 표현한다. 두 목록의 길이가 항상 같다는 조건이 없는데 모두 n으로 부르면 한쪽만 커지는 상황을 설명할 수 없다. 어떤 변수가 고정 상수이고 어떤 변수가 증가할 수 있는지도 명시한다.
예제 코드
for value in [8, 16, 32]:
print(value, value.bit_length())실행 결과
8 4
16 5
32 6비용 모델: 한 줄이 한 번의 연산은 아니다
기본 연산을 일정 비용으로 세는 모델에서는 고정 크기 정수의 덧셈이나 배열 인덱스 접근을 한 단위로 볼 수 있다. 이런 단순화는 알고리즘의 구조를 비교하는 데 유용하지만 모든 언어의 모든 표현식이 상수 시간이라는 뜻은 아니다.
sorted(values)는 코드 한 줄이지만 정렬 작업을 수행한다. 긴 문자열의 비교, 슬라이스 생성, 목록 결합, 큰 정수 곱셈도 입력 크기에 따라 비용이 달라질 수 있다. 루프 밖에 있는 한 줄이라도 전체 비용을 지배할 수 있다. 반대로 여러 문장을 고정 횟수 실행하는 부분은 전체 증가율에서 상수 항으로 묶을 수 있다.
모델의 기본 연산과 실제 구현의 차이를 알면 추상 분석을 잘못 적용하지 않게 된다. Python의 무한 정밀도 정수와 기계어 한 워드에 들어가는 정수는 같은 비용 가정이 아니다. 파일 읽기나 네트워크 요청은 대기 시간과 전송량, 시스템 상태에 영향을 받으므로 RAM 연산 수만으로 응답 시간을 설명할 수 없다.
실무 분석에서는 먼저 비교 횟수나 자료 이동량처럼 의미 있는 비용을 세고, 이후 프로파일링으로 실제 병목을 확인한다. 더 정밀한 분석이 필요하면 키 길이, 디스크 블록 접근 수, 통신량 같은 변수를 추가한다. 모델은 현실을 숨기기 위한 것이 아니라 어떤 비용을 설명하는지 명확하게 만들기 위한 도구다.
빅 오 O: 점근적 상한
T(n)이 O(g(n))이라는 말은 충분히 큰 n에서 T(n)이 어떤 양의 상수 배의 g(n)을 넘지 않는다는 뜻이다. 상수 c와 기준 n₀가 존재하여 n≥n₀일 때 T(n)≤c·g(n)으로 묶을 수 있으면 된다. 작은 입력 몇 개의 값이나 정확한 실행 초를 지정하는 표기는 아니다.
T(n)=3n+7이라면 n≥1에서 3n+7≤10n이므로 O(n)이라고 말할 수 있다. 동시에 O(n²)이라는 더 느슨한 상한도 참이다. 일상적인 설명에서는 보통 유용하고 타이트한 차수의 상한을 말하지만, O 기호 자체가 반드시 가장 타이트한 차수를 뜻하지는 않는다.
O(n)이 “최악의 경우”의 동의어는 아니다. 최악 실행 시간 함수를 O(n)으로 묶을 수도 있고 평균 실행 시간 함수를 O(n)으로 묶을 수도 있다. 어떤 함수를 분석하는지와 그 함수의 상한 표기를 구분한다. 이 구분을 놓치면 평균 O(1)과 최악 O(n)을 모순으로 오해하기 쉽다.
상수 배를 생략한다고 상수가 실제로 중요하지 않다는 뜻도 아니다. 1000n과 2n은 같은 차수지만 동일한 입력에서 작업량은 다르다. 점근적 분석은 증가율을 비교하고 실제 크기에서의 선택은 상수와 측정 결과도 함께 본다.
Ω와 Θ: 하한과 타이트한 증가율
Ω(g(n))는 충분히 큰 입력에서 일정한 양의 상수 배 g(n)보다 작아지지 않는 하한을 표현한다. Θ(g(n))는 상한과 하한이 같은 차수로 묶인다는 뜻이다. T(n)=3n+7은 Θ(n)으로 표현할 수 있다.
하한이라고 해서 항상 최선 실행 시간을 뜻하는 것은 아니다. 특정 알고리즘의 최악 실행 시간에 대한 하한을 말할 수도 있고, 주어진 모델에서 문제를 푸는 모든 알고리즘이 필요로 하는 작업량의 하한을 말할 수도 있다. 후자는 하나의 구현 분석보다 강한 주장이다.
비교 기반 정렬의 Ω(n log n) 하한은 비교를 통해 순서를 알아내는 모델과 일반 입력에 대한 것이다. 제한된 범위의 정수 값을 인덱스로 사용하는 알고리즘에는 다른 정보가 있으므로 같은 하한을 그대로 적용하지 않는다. 하한을 인용할 때 계산 모델과 입력 조건을 빼면 잘못된 결론이 된다.
분석 결과가 단순한 상한뿐이면 Θ라고 쓰기 전에 같은 차수의 하한도 성립하는지 확인한다. 조기 종료가 있는 코드에서 모든 입력이 n번 반복하는 것은 아닐 수 있다. 최악 입력을 구성하거나 실제 반복 수의 식을 구해 어떤 경우를 설명하는지 분명히 한다.
순차 반복: 더하기 규칙
두 반복문을 순서대로 실행하면 비용을 더한다. 첫 번째가 n회, 두 번째가 m회라면 기본 작업 횟수는 n+m이다. 반복문이 두 개 있다는 이유로 n·m을 곱하지 않는다. 같은 입력을 두 번 순회한다면 2n이므로 Θ(n)이다.
아래 count_sequential(3,5)는 8을 반환한다. 각 반복의 몸체가 상수 시간이라고 가정했을 때의 카운터다. 실제 몸체에서 길이 n의 문자열을 비교한다면 그 비용을 추가해야 한다. 반복 횟수와 한 번의 반복 비용을 따로 계산하면 이런 누락을 줄일 수 있다.
같은 변수 n의 다항 항을 더할 때는 충분히 큰 n에서 가장 큰 차수가 증가율을 지배한다. n²+10n+100은 Θ(n²)이다. 그러나 n과 m이 독립 변수이면 n+m에서 한쪽을 임의로 버릴 수 없다. m≤n이라는 조건이 있을 때에만 O(n) 같은 단순화가 가능하다.
예제 코드
def count_sequential(n, m):
count = 0
for _ in range(n):
count += 1
for _ in range(m):
count += 1
return count
print(count_sequential(3, 5))
print(count_sequential(10, 10))실행 결과
8
20중첩 반복: 곱하기가 맞는 조건
바깥 반복의 각 단계에서 안쪽 반복을 m번 수행하면 전체 횟수는 n·m이다. 두 루프의 범위가 모두 n이면 n²이다. 아래 직사각형 반복은 n=3,m=4일 때 12번 실행된다.
하지만 중첩 반복이라는 모양만으로 O(n²)이라고 판단하면 안 된다. 안쪽 범위가 바깥 인덱스에 따라 달라지거나, 두 포인터가 전체 실행에서 한 방향으로만 움직이거나, 중간에 종료하면 합계를 따로 계산해야 한다. 코드의 들여쓰기 깊이는 복잡도의 정의가 아니다.
또한 안쪽 루프가 상수 10회라면 10n으로 Θ(n)이다. 그 10이 실제로 고정된 규칙인지, 입력으로 주어진 값 k를 예제에서만 10으로 둔 것인지 구별한다. 상수로 취급한 매개변수가 배포 환경에서 커질 수 있다면 분석에 다시 포함해야 한다.
예제 코드
def rectangle(n, m):
count = 0
for i in range(n):
for j in range(m):
count += 1
return count
print(rectangle(3, 4))
print(rectangle(10, 10))실행 결과
12
100삼각형 반복과 합의 계산
안쪽 반복이 i번씩 실행되면 전체 횟수는 0+1+2+…+(n-1)이다. 이는 n(n-1)/2이고 Θ(n²)이다. 전체 n²의 절반쯤이라고 해서 차수가 선형으로 바뀌지 않는다. 상수 배와 증가율을 구분하는 대표적인 예다.
아래 n=5이면 10, n=10이면 45다. 서로 다른 두 인덱스의 순서 없는 쌍을 한 번씩 확인할 때 이런 형태가 나온다. 자기 자신과의 쌍을 포함하거나 양방향 쌍을 모두 세면 정확한 식은 달라지지만 이 경우 차수는 여전히 이차다.
이와 달리 안쪽 반복이 매번 i를 두 배씩 키우는 형태라면 로그 합이 생길 수 있다. 반복 횟수를 식으로 쓰고 합을 평가하는 습관이 필요하다. 경계 인덱스가 0부터인지 1부터인지에 따라 정확한 횟수가 달라져도 점근 차수는 같을 수 있으므로 두 종류의 결론을 구분한다.
예제 코드
def triangle(n):
count = 0
for i in range(n):
for j in range(i):
count += 1
return count
for n in [5, 10]:
print(triangle(n), n * (n - 1) // 2)실행 결과
10 10
45 45로그 반복: 두 배씩 증가하는 변수
i가 1에서 시작해 매번 두 배가 되고 n에 도달하면 멈춘다면 반복 횟수는 n을 2의 거듭제곱으로 덮는 데 필요한 단계 수다. n≥1에서 대략 log₂n이며 정확한 횟수는 경계 조건에 따라 올림 또는 내림이 달라진다.
아래 while i<n은 n=1에서 0회, n=8에서 3회, n=9에서 4회다. n이 두 배가 되어도 단계가 하나 정도 늘어나는 이유를 직접 볼 수 있다. 로그의 밑이 고정된 2나 10이면 상수 배 차이이므로 점근 차수 O(log n)에서 보통 생략한다.
변수를 곱한다고 무조건 로그 시간이 되는 것은 아니다. 루프 몸체에서 i개 원소를 처리하면 비용은 1+2+4+…로 합쳐져 O(n)이 될 수 있다. 반복 단계 수와 각 단계의 작업량을 함께 계산해야 한다.
예제 코드
def doubling_steps(n):
i = 1
count = 0
while i < n:
count += 1
i *= 2
return count
for n in [1, 8, 9, 16]:
print(n, doubling_steps(n))실행 결과
1 0
8 3
9 4
16 4기하급수 합: 단계마다 일이 늘어날 때
크기를 두 배씩 늘리며 각 단계의 모든 원소를 복사하면 마지막 단계가 가장 크다. 1+2+4+…+2^k는 2^(k+1)-1이므로 마지막 항의 상수 배 이내다. 단계가 log n개여도 전체 작업은 Θ(n)이 될 수 있다.
아래 n=8에서 크기 1,2,4를 복사하므로 합계는 7이고, n=16에서는 15다. 이 계산은 뒤에서 다룰 동적 배열의 확장 비용과도 연결된다. 매번 모든 항을 n으로 상한 잡아 n log n이라고 하면 유효한 느슨한 상한일 수 있어도 실제 증가율을 놓친다.
정확한 분석이 어려울 때 상한을 먼저 구하는 것은 유용하다. 다만 그 상한이 타이트한지, 더 정밀하게 합을 계산할 수 있는지를 구분한다. 최적화 전후의 차이를 평가할 때는 지나치게 느슨한 상한이 중요한 정보를 감출 수 있다.
예제 코드
def copied_items(n):
size = 1
copied = 0
while size < n:
copied += size
size *= 2
return copied
print(copied_items(8))
print(copied_items(16))실행 결과
7
15두 포인터: 중첩 while도 선형일 수 있다
포인터가 전체 실행에서 뒤로 돌아가지 않고 각각 최대 n번 움직인다면 중첩 반복처럼 보여도 총 이동 수는 O(n)일 수 있다. 바깥 루프마다 안쪽이 처음부터 n번 다시 도는지, 이전 위치에서 계속 진행하는지 확인해야 한다.
아래는 음이 아닌 정수 배열에서 합이 limit 이하인 가장 긴 연속 구간의 길이를 구한다. 오른쪽 끝을 하나씩 늘리고 합이 초과하면 왼쪽 끝을 앞으로 옮긴다. 각 원소는 한 번 더해지고 최대 한 번 빠진다. 입력 [2,1,3,1,1], limit=4에서 가장 긴 길이는 2이고 왼쪽 이동은 3회다.
음수가 있으면 오른쪽을 늘릴 때 합이 줄어들 수도 있으므로 같은 축소 논리가 최적 구간을 보존한다고 할 수 없다. 이 알고리즘은 비음수 원소와 음이 아닌 limit를 전제로 한다. 선형 시간이라는 분석이 정확해도 알고리즘의 적용 전제가 틀리면 답은 잘못될 수 있다.
예제 코드
def longest_bounded(values, limit):
left = total = best = moves = 0
for right, value in enumerate(values):
total += value
while total > limit:
total -= values[left]
left += 1
moves += 1
best = max(best, right - left + 1)
return best, moves
print(longest_bounded([2, 1, 3, 1, 1], 4))실행 결과
(2, 3)최선·최악·평균은 같은 크기의 입력을 비교한다
최선과 최악은 작은 입력과 큰 입력을 비교하는 말이 아니다. 길이가 같은 n인 입력들 사이에서 내용에 따라 작업량이 달라지는 경우를 구분한다. 선형 탐색은 첫 원소에서 찾으면 한 번, 없거나 마지막에서 찾으면 n번 비교한다.
아래 길이 4인 배열에서 비교 횟수는 1,4,4다. 모두 같은 크기지만 찾는 값의 위치와 부재 여부가 다르다. 최악 Θ(n), 최선 Θ(1)이라는 표현은 서로 모순이 아니다. 서로 다른 실행 시간 함수를 분석한 결과다.
평균은 입력 분포가 있어야 정의된다. 성공하는 위치가 0부터 n-1까지 균등하다면 비교 횟수 평균은 (n+1)/2다. 실패 가능성과 각 위치의 조회 빈도가 다르면 평균도 달라진다. 실제 서비스에서 자주 찾는 항목을 앞에 두는 전략은 이 분포를 활용하지만 갱신 비용과 다른 조회 패턴도 고려해야 한다.
최악 시간 보장은 지연 상한을 중요하게 보는 환경에서 의미가 있다. 평균이 좋다고 드물게 매우 느린 요청을 허용할 수 있는 것은 아니다. 반대로 모든 상황에 최악 보장만 요구하면 평균적으로 더 단순하고 유리한 방법을 놓칠 수 있으므로 요구사항에 맞춰 비교한다.
예제 코드
def comparisons(values, target):
count = 0
for value in values:
count += 1
if value == target:
break
return count
for target in [2, 8, 99]:
print(comparisons([2, 4, 6, 8], target))실행 결과
1
4
4기댓값과 무작위성: 무엇에 대한 평균인가
기대 실행 시간은 확률 변수를 명시해야 한다. 입력이 어떤 분포에서 나온다고 가정할 수도 있고, 고정된 입력에 대해 알고리즘이 내부에서 고르는 난수에 대한 기댓값을 분석할 수도 있다. 둘은 다른 보장이다.
무작위 피벗을 선택하는 정렬을 생각하면 입력을 고정해도 선택한 피벗에 따라 실행 흐름이 달라진다. 반면 항상 첫 원소를 피벗으로 고르고 입력이 무작위라고 가정하는 분석은 입력 분포에 의존한다. 공격자가 입력을 선택할 수 있는 환경이라면 이 차이가 중요할 수 있다.
기대 O(n log n)이라고 해서 모든 실행이 그 범위 안에서 일정하게 끝난다는 뜻은 아니다. 꼬리 확률이나 높은 확률의 보장이 필요한지 별도로 검토한다. 실제 요청의 95백분위·99백분위 지연은 점근적 기대 시간 표기와 같은 수치가 아니며 측정과 모델링이 필요하다.
무작위 벤치마크는 시드와 생성 분포를 기록해 재현할 수 있게 한다. 여러 시드를 실행해도 이론적 확률 보장을 증명하는 것은 아니지만 구현 오류와 특정 분포의 편향을 찾는 데 유용하다. 우연히 유리한 입력 하나를 전체 성능의 대표로 삼지 않는다.
분할 상환 분석: 비싼 한 번을 연산열 전체로 보기
분할 상환 분석은 여러 연산을 연속해서 수행할 때 총비용을 연산 수에 나눠 설명한다. 입력의 확률 분포를 가정하는 평균 분석과 다르다. 어떤 연산은 비싸더라도 그런 연산이 자주 일어날 수 없다는 구조를 이용한다.
동적 배열이 꽉 찰 때 용량을 두 배로 늘린다고 하자. 보통 추가는 한 칸 쓰면 되지만 확장 시에는 기존 원소를 복사한다. n개의 추가 중 복사량은 1+2+4+…처럼 합쳐져 O(n)이며 각 추가의 쓰기 n회와 함께 총 O(n)이다. 따라서 추가 한 번의 분할 상환 비용은 O(1)이지만 확장하는 특정 한 번은 O(n)일 수 있다.
아래는 실제 메모리 할당 대신 두 배 확장 정책의 원소 쓰기·복사 횟수를 계산한다. 8개 추가에서는 총비용 15, 마지막 한 번의 최대 비용은 5다. 16개에서는 31과 9다. 총비용은 선형으로 늘지만 개별 비싼 연산의 존재도 함께 보인다.
모든 동적 배열 구현이 정확히 두 배 정책을 사용하는 것은 아니다. 이 예제는 분석 원리를 보여주는 모델이다. 실시간 응답처럼 한 번의 지연을 제한해야 한다면 분할 상환 상수 시간만으로 충분하지 않을 수 있고, 사전 용량 확보나 작업 분산 같은 전략을 검토한다.
예제 코드
def append_costs(n):
size = 0
capacity = 1
costs = []
for _ in range(n):
copied = 0
if size == capacity:
copied = size
capacity *= 2
costs.append(copied + 1)
size += 1
return sum(costs), max(costs, default=0)
print(append_costs(8))
print(append_costs(16))실행 결과
(15, 5)
(31, 9)재귀식: 호출 한 번의 작업과 하위 호출
재귀 알고리즘은 현재 호출의 작업량과 하위 호출의 비용을 합쳐 식을 세울 수 있다. 이진 탐색처럼 문제 크기를 절반으로 줄인 한 부분만 처리하면 T(n)=T(n/2)+Θ(1) 형태가 된다. 병합 정렬처럼 두 부분을 처리하고 선형으로 합치면 T(n)=2T(n/2)+Θ(n) 형태다.
중요한 것은 재귀 호출이 몇 개인지, 각 크기가 얼마인지, 호출 밖에서 무엇을 하는지다. 중간 위치를 계산하고 배열 인덱스 범위만 넘기는 이진 탐색과 매번 절반 배열을 복사하는 구현은 재귀 깊이는 같아도 전체 비용이 다를 수 있다.
기저 조건과 반올림도 필요하다. n이 2의 거듭제곱이 아닐 때 부분 크기가 바닥·천장으로 나뉘어도 큰 차수는 유지될 수 있지만 정확한 연산 수를 검증하려면 구체적인 식을 사용한다. n=0이나 n=1에서 어떻게 멈추는지 빠뜨리면 분석 이전에 구현이 끝나지 않을 수 있다.
마스터 정리는 특정 형태의 재귀식을 빠르게 분석하는 도구다. 모든 재귀에 적용되는 만능 공식은 아니다. 하위 문제 크기가 n-1이거나 부분 크기가 크게 비대칭이고 비용이 복잡하면 재귀 트리, 합, 치환 같은 다른 방법으로 분석한다. 공식 이름보다 식이 알고리즘을 정확히 나타내는지가 먼저다.
병합 정렬의 재귀 트리
크기 n을 절반씩 둘로 나누면 깊이마다 부분 문제 수는 늘고 각 크기는 줄어든다. 각 깊이에서 병합하는 총 원소 수는 n에 비례한다. 깊이가 log₂n에 비례하므로 전체는 Θ(n log n)이 된다.
아래 모델은 n을 2의 거듭제곱으로 제한하고 각 내부 호출에서 n만큼의 병합 비용을 더한다. n=8이면 24, n=16이면 64다. 각각 n·log₂n과 같다. 실제 구현의 비교 횟수와 완전히 같은 수치를 주장하는 것이 아니라 재귀식의 층별 비용을 확인하는 모델이다.
재귀 깊이 log n만 보고 공간도 반드시 O(log n)이라고 할 수는 없다. 부분 배열과 병합 결과를 저장하면 추가 공간이 필요하다. 호출 스택 공간과 데이터 버퍼 공간을 합쳐 보아야 한다. 전체 실행 중 할당된 누적 바이트와 동시에 살아 있는 최대 메모리도 서로 다른 지표다.
예제 코드
def merge_work(n):
if n <= 1:
return 0
return merge_work(n // 2) + merge_work(n // 2) + n
for n in [8, 16]:
print(n, merge_work(n))실행 결과
8 24
16 64반복 재귀와 메모이제이션의 변화
피보나치의 단순 재귀는 같은 하위 문제를 여러 번 계산한다. 호출 수를 C(n)=C(n-1)+C(n-2)+1로 세면 빠르게 증가한다. 아래 n=10에서는 함수가 177번 호출된다. 캐시를 둔 버전은 같은 입력의 본문을 한 번씩 계산하여 실제 본문 실행이 11번이다. 두 결과는 모두 55다.
계산한 상태 수가 줄어든 이유는 단순히 재귀를 사용했거나 반복문으로 바꿨기 때문이 아니다. 같은 상태를 중복 계산하지 않도록 결과를 저장했기 때문이다. 동적 계획법의 시간은 보통 상태 수와 상태당 전이 비용을 함께 계산한다. 상태가 n개여도 각 상태에서 n개 후보를 검사하면 O(n²)일 수 있다.
캐시는 메모리를 사용하고, 재귀 방식은 호출 깊이가 남는다. 피보나치의 마지막 값만 필요하면 반복문으로 이전 두 값만 유지할 수 있다. 큰 수의 덧셈 비용까지 포함하면 “n번 덧셈”과 “전체 비트 연산 시간이 선형”은 다른 주장이다.
예제 코드
from functools import lru_cache
plain_calls = 0
def plain(n):
global plain_calls
plain_calls += 1
return n if n < 2 else plain(n - 1) + plain(n - 2)
cached_calls = 0
@lru_cache(maxsize=None)
def cached(n):
global cached_calls
cached_calls += 1
return n if n < 2 else cached(n - 1) + cached(n - 2)
print(plain(10), plain_calls)
print(cached(10), cached_calls)실행 결과
55 177
55 11여러 입력 변수와 그래프 표현
그래프 탐색은 정점 수 V와 간선 수 E를 함께 사용한다. 인접 목록에서 각 정점과 간선을 한정된 횟수만 처리하면 O(V+E)다. 간선이 거의 없는 그래프와 거의 모든 정점 쌍이 연결된 그래프는 같은 V여도 E가 크게 다르다.
인접 행렬을 사용해 각 정점에서 모든 후보 정점을 확인하면 O(V²) 작업이 생길 수 있다. “BFS는 항상 O(V+E)”라는 말에는 자료 표현과 이웃 순회 비용의 전제가 들어 있다. 인접 목록을 만드는 비용까지 분석 범위에 포함하는지도 표시한다.
두 문자열의 길이가 n,m인 동적 계획법은 표 크기가 n·m일 수 있다. 한쪽 길이가 작게 고정되어 있다면 실제 비용이 달라 보일 수 있지만 일반식에서 임의로 같은 n으로 바꾸지 않는다. 데이터베이스 조인이나 두 집합의 비교도 각 입력 크기를 별도로 유지하면 비용을 더 정확히 설명할 수 있다.
출력 크기 z가 중요한 문제는 O(n+m+z)처럼 출력량을 포함해 표현할 수 있다. 입력이 작아도 조합 결과가 매우 많을 수 있고, 모든 결과를 실제로 출력하는 알고리즘은 그 개수만큼의 작업을 피할 수 없다. 결과를 지연 생성한다고 모든 결과를 소비하는 총비용이 없어지는 것은 아니다.
숨겨진 복사: 슬라이스와 반복 결합
Python 목록의 슬라이스는 새 목록을 만들며 포함된 원소 참조를 복사한다. 반복마다 점점 긴 접두 구간을 복사하면 1+2+…+n개의 참조를 이동한다. 코드에 루프가 하나만 보여도 총 복사량은 Θ(n²)이다.
아래는 길이 5인 목록의 접두 구간을 차례로 복사하고 길이를 더해 15를 얻는다. 함수 호출 안에서 복사가 숨어 있다면 호출자만 보고 복잡도를 판단하기 어렵다. 구현 언어와 라이브러리의 의미를 확인해야 한다.
불변 문자열을 반복 결합하는 코드도 언어와 구현에 따라 누적 복사 비용이 생길 수 있다. 어떤 런타임의 특정 최적화에 기대어 일반적인 상수 시간 결합으로 설명하지 않는다. 문자열 조각을 모아 한 번 결합하는 API를 비교하되, 실제 메모리와 입력 크기에 맞춰 측정한다.
반대로 슬라이스가 항상 복사인 언어만 있는 것은 아니다. 뷰를 만드는 API는 원본 공유와 수명 문제가 생길 수 있다. 복사 비용을 없애는 선택은 의미와 소유권도 바꿀 수 있으므로 성능과 동작을 함께 검토한다.
예제 코드
values = [1, 2, 3, 4, 5]
copied = 0
for end in range(1, len(values) + 1):
prefix = values[:end]
copied += len(prefix)
print(copied)실행 결과
15해시 조회와 문자열 비교 비용
사전 조회를 기대 O(1)이라고 설명할 때는 해시 계산과 키 비교, 충돌 처리에 대한 모델이 있다. 길이 L인 문자열의 해시를 새로 계산하거나 긴 공통 접두사를 가진 문자열을 비교하면 L에 의존하는 작업이 생길 수 있다. 원소 수 n만 보는 분석이 충분한지 확인한다.
한 번 계산한 해시를 객체가 저장하는 구현과 매번 다시 계산하는 구현은 반복 조회에서 다르게 동작할 수 있다. 키가 정수인지 문자열인지 사용자 정의 객체인지에 따라 해시와 동등성 검사 비용도 달라진다. 사용자 정의 비교 함수가 내부에서 파일을 읽는다면 단순 비교 기반 분석의 전제가 무너진다.
충돌이 적도록 설계된 정상 사용의 기대 비용과 최악 비용을 구분한다. 비정상 입력에 대한 방어, 테이블 확장, 삭제 흔적 관리 같은 구현 요소도 실제 성능에 영향을 준다. 특정 언어 버전의 구현 세부를 다른 제품의 해시 테이블에 그대로 적용하지 않는다.
정렬에서 비교 한 번이 O(L)이라면 단순히 O(n log n)번 비교한다는 말과 전체 문자 처리 비용은 다를 수 있다. 반대로 비교 키를 미리 계산해 두면 반복 비용을 줄일 수 있지만 추가 메모리와 전처리 시간이 든다. 분석 단위를 명시하면 이런 선택을 설명하기 쉽다.
전처리와 반복 질의의 손익
한 번의 질의가 빠른 방법이 전체 작업에서도 빠른지는 준비 비용에 달려 있다. 목록의 선형 탐색은 질의 q개에 최악 O(qn)이다. 정렬 후 이진 탐색은 비교 기반 정렬을 사용하면 O(n log n+q log n) 형태가 된다. 정렬 때문에 원래 위치가 바뀌는 의미도 고려해야 한다.
q가 작고 n도 작다면 전처리가 오히려 부담일 수 있다. 같은 자료를 오래 재사용하고 질의가 많다면 준비 비용을 나눠 감수할 수 있다. 자료가 갱신될 때 인덱스를 유지하거나 다시 만드는 비용을 빼면 실제 시스템의 비용을 과소평가한다.
누적 합은 O(n) 준비 후 구간 합을 O(1)에 얻지만 값 변경 시 많은 접두 합이 영향을 받는다. 사전은 정확한 키 조회에 적합하지만 정렬된 범위 순회에는 다른 구조가 필요할 수 있다. 하나의 연산만 빠르게 만들기보다 전체 작업의 비율을 기준으로 선택한다.
캐시도 같은 관점으로 본다. 캐시 적중 시 비용뿐 아니라 미스, 만료, 메모리 상한과 갱신 정합성 비용이 있다. “캐시를 쓰면 O(1)”이라는 문장은 어떤 연산과 상태를 말하는지 빠져 있으면 실용적인 분석이 되기 어렵다.
공간 복잡도와 지연 평가
시간과 공간은 교환 관계를 가질 수 있다. 중간 결과를 저장하면 재계산을 줄일 수 있지만 메모리가 늘어난다. 반대로 일부 상태를 버리고 필요할 때 다시 계산하면 공간을 줄이는 대신 시간이 늘 수 있다. 원하는 출력과 재사용 횟수에 맞춰 선택한다.
제너레이터는 결과를 한 번에 모두 저장하지 않고 필요할 때 생성할 수 있다. 그러나 모든 결과를 순회하면 생성 작업의 총량은 여전히 필요하다. 제너레이터 생성 시점만 측정하고 결과 소비를 제외하면 전체 연산이 상수 시간인 것처럼 잘못 보일 수 있다.
출력 자체가 n개 항목이라면 출력 저장 공간을 포함할 때 Ω(n)이 필요하다. 보조 공간 O(1)이라는 설명은 출력과 입력을 제외한 작업 상태만 세는 경우가 많다. 어떤 공간을 포함했는지 명시하지 않으면 서로 다른 구현의 수치를 비교하기 어렵다.
재귀 호출은 스택 공간을 사용한다. 꼬리 재귀 형태라고 모든 언어가 자동으로 스택을 제거하는 것은 아니다. 구현 환경의 최적화와 제한을 확인하고, 깊이가 입력 크기에 비례하는 알고리즘은 명시적 스택이나 반복 구조를 검토한다.
의사다항 시간과 지수적 후보 수
금액 A까지의 표를 채우는 동전 문제나 배낭 문제의 일부 동적 계획법은 A의 값에 다항식으로 비례할 수 있다. 그러나 A를 이진수로 입력받으면 입력 길이는 log A에 비례하므로 이것이 입력 길이에 대한 다항 시간이라는 뜻은 아니다. 이런 구분에서 의사다항이라는 용어를 사용한다.
반면 n개 항목의 모든 부분집합은 2^n개다. 각 후보를 실제로 생성하면 후보 수 자체가 빠르게 증가한다. 아래 n=10,20,30에서 각각 1024,1048576,1073741824가 된다. n을 조금 늘렸는데 실행이 갑자기 감당하기 어려워지는 이유를 설명한다.
지수 시간이라는 분석이 작은 입력에서도 무조건 사용할 수 없다는 뜻은 아니다. n이 작게 제한되거나 가지치기, 문제 분해와 매개변수화가 가능하면 실용적인 해법이 될 수 있다. 반대로 다항 시간이라는 이유만으로 현실적으로 충분히 빠른 것도 아니다. 큰 차수와 상수, 자료 크기를 함께 본다.
복잡도 분류는 문제의 정확한 형식에 적용한다. 최적화 문제와 결정 문제, 정확한 해와 근사해, 일반 입력과 제한된 입력을 섞지 않는다. NP-난해라는 말만으로 모든 실용적 접근을 포기하거나, 작은 벤치마크 성공만으로 일반 문제를 빠르게 해결했다고 주장하지 않는다.
예제 코드
for n in [10, 20, 30]:
print(n, 2 ** n)실행 결과
10 1024
20 1048576
30 1073741824측정으로 분석을 확인하는 방법
입력 크기를 단계적으로 늘리면서 실제 실행 시간이나 연산 횟수를 비교하면 증가율을 관찰할 수 있다. n을 두 배로 했을 때 선형 모델은 대략 두 배, 이차 모델은 대략 네 배가 된다. 하지만 작은 입력에서는 고정 비용과 측정 잡음이 커서 이런 비율이 뚜렷하지 않을 수 있다.
입력 준비와 측정할 함수를 분리하고 반복 횟수, 런타임 버전, 하드웨어와 데이터 분포를 기록한다. 정렬된 입력 하나만으로 일반 정렬 성능을 판단하지 않는다. 같은 객체를 반복 사용하면서 캐시가 따뜻해지는 경우와 매번 새로운 자료를 만드는 경우도 구분한다.
시간 측정에는 timeit 같은 도구를 사용할 수 있고, 함수별 비용을 조사할 때는 해당 Python 버전에 맞는 프로파일러를 사용한다. 계측 도구의 오버헤드와 포함 범위를 확인한다. 이 문서에서는 특정 기기의 시간 수치를 일반화하지 않기 위해 결정적인 카운터 예제를 사용했다.
실험으로 얻은 유한한 데이터만으로 점근적 상한을 증명할 수는 없다. 분석이 예상한 증가율과 측정이 다르면 숨겨진 복사나 비용 모델, 입력 분포를 조사한다. 측정과 이론은 경쟁하는 방법이 아니라 서로 빠진 가정을 찾는 데 도움을 주는 방법이다.
실전 분석 예제: 목록을 반복 검색하는 코드
사용자 ID n개와 요청 ID q개가 있고, 각 요청이 목록에 있는지 확인한다고 하자. 요청마다 목록의 in 연산을 사용하면 최악 q·n번에 비례하는 비교가 필요하다. 요청 목록이 작을 때는 간단하지만 조회가 반복될수록 같은 자료를 다시 순회한다.
사전을 대신해 집합을 만들면 중복 ID를 하나로 모으고 기대 상수 시간의 포함 검사를 사용할 수 있다. 일반적인 해시 비용 가정 아래 구축 O(n), 질의 O(q), 저장 O(n) 형태가 된다. 정확한 중복 개수나 원래 순서가 필요하면 집합만으로 요구사항을 충족하지 못한다.
아래 두 구현은 같은 존재 여부 [True,False,True]를 반환한다. 빠른 버전을 만들었다면 결과 계약이 같음을 확인하는 것이 먼저다. ID가 해시 가능한 값이라는 전제도 추가된다. 목록 안의 임의 객체가 모두 집합의 원소로 사용 가능한 것은 아니다.
실제 변경 판단에는 한 번의 구축을 얼마나 재사용하는지, 자료 갱신과 메모리 상한, 키 길이와 충돌 조건을 포함한다. 이 예제의 O(n+q)는 전체 요청을 처리하는 기대 비용 모델이며 개별 질의의 최악 지연 보장을 선언하는 것이 아니다.
예제 코드
ids = [10, 20, 30, 40]
queries = [20, 99, 10]
slow = [query in ids for query in queries]
known = set(ids)
fast = [query in known for query in queries]
print(slow)
print(fast)
assert slow == fast실행 결과
[True, False, True]
[True, False, True]검산: 예측한 식을 여러 크기에서 대조하기
다음 코드는 앞의 triangle, doubling_steps, copied_items, append_costs 정의 뒤에 붙여 실행한다. n=1부터 64까지 삼각형 반복 횟수, 두 배 증가 단계, 기하급수 복사량과 동적 배열 총비용의 상한을 확인한다. 총 256개의 조건을 검사한다.
삼각형 반복은 정확한 식과 비교하고, 로그 단계는 2의 거듭제곱이 n을 처음 덮는 성질을 검사한다. 복사량과 추가 비용은 각각 선형 상한을 확인한다. 정확한 횟수와 상한이라는 서로 다른 형태의 분석을 테스트에 표현한 것이다.
이 검사는 작은 범위에서 구현과 식의 불일치를 찾는 용도다. 모든 n에 대한 증명은 합의 공식과 불변식 같은 논리로 별도 설명해야 한다. 검산이 통과했다는 이유로 지원하지 않는 입력 타입이나 음수 크기까지 계약에 포함하지 않는다.
예제 코드
checks = 0
for n in range(1, 65):
assert triangle(n) == n * (n - 1) // 2
checks += 1
steps = doubling_steps(n)
assert 2 ** steps >= n and (steps == 0 or 2 ** (steps - 1) < n)
checks += 1
assert copied_items(n) < 2 * n
checks += 1
assert append_costs(n)[0] < 3 * n
checks += 1
print(checks)실행 결과
256분석 결과를 문서에 쓰는 법
“이 함수는 O(n)”이라고만 쓰기보다 n은 원소 수이고 비교와 인덱스 접근을 상수 시간으로 보며, 정렬된 배열에서 최악 O(log n)번 비교한다는 식으로 범위를 명시한다. 준비 비용과 출력 비용, 추가 메모리를 포함했는지도 덧붙이면 다른 사람이 같은 분석을 재현하기 쉽다.
가장 흔한 실수는 중첩 루프 수만 세기, 라이브러리 호출을 상수로 보기, O를 최악의 동의어로 쓰기, 평균 분포를 생략하기, 분할 상환 보장을 개별 지연 보장으로 바꾸기다. 큰 수의 비트 길이나 두 입력 크기를 숨기는 것도 주의한다.
알고리즘 선택에는 정확성이 먼저다. 빠르지만 전제 조건이 맞지 않는 이진 탐색이나 음수 가중치에서 잘못 적용한 최단 경로 방법은 좋은 해법이 아니다. 올바른 후보들 사이에서 작업량·메모리·구현 복잡성과 실제 성능을 비교한다.
복잡도 분석의 목적은 기호를 짧게 만드는 것이 아니라 입력이 커질 때 어느 비용이 문제인지 설명하는 데 있다. 어떤 가정 아래 무엇을 줄였는지, 그 대신 어떤 비용이 생기는지 말할 수 있으면 성능 개선과 코드 리뷰에 실질적으로 활용할 수 있다.