시간 복잡도와 공간 복잡도: 알고리즘 효율성 분석
복잡도, 결국 반복문 몇 번 도는지 세는 거였다
솔직히 처음에 O(n log n) 같은 표기를 봤을 때 “이걸 왜 외워야 하지?” 싶었습니다. 수학 수업도 아니고.
그런데 백준에서 시간 초과를 몇 번 맞고 나니까 생각이 바뀌었습니다. 분명 로직은 맞는데 n이 10만만 넘어가면 터지는 코드가 있고, 같은 문제를 다른 방식으로 풀면 100만이어도 잘 돌아가는 코드가 있었거든요. 그 차이가 뭔지 설명해주는 게 복잡도 분석이었습니다.
왜 실행 시간을 직접 재면 안 되나
처음엔 그냥 time 찍어서 비교하면 되지 않나 싶었습니다.
import time
def measure_time(func, *args):
start = time.time()
result = func(*args)
end = time.time()
return result, end - start
# 예시
arr = list(range(10000))
result, exec_time = measure_time(find_number_v1, arr, 5000)
print(f"실행 시간: {exec_time:.6f}초")근데 이게 같은 코드를 집 데스크탑이랑 노트북에서 돌리면 결과가 다릅니다. 백그라운드에서 뭐가 돌고 있느냐에 따라서도 달라지고요. 그래서 하드웨어에 의존하지 않는 기준이 필요했고, 그게 연산 횟수를 세는 방식입니다.
def count_operations(arr):
count = 0
for i in range(len(arr)): # n번 반복
count += 1 # 1번 연산
return count
# 입력 크기가 n일 때 연산 횟수 = n이렇게 “입력이 n개일 때 대략 몇 번 연산하느냐”로 보면, 컴퓨터가 빠르든 느리든 알고리즘 자체의 효율을 비교할 수 있게 됩니다.
Big-O가 하는 일
Big-O는 “최악의 경우 이 정도까지 걸릴 수 있다”는 상한선을 표현합니다. 세부적인 연산 횟수보다 큰 그림을 보는 거라서, 계산할 때 규칙이 있습니다.
- 상수는 버린다: O(2n)이면 그냥 O(n)
- 계수도 버린다: O(3n²)이면 O(n²)
- 가장 큰 항만 남긴다: O(n² + n)이면 O(n²)
- 로그 밑은 신경 안 쓴다: O(log₂ n)이든 O(log₁₀ n)이든 O(log n)
처음에 “상수를 왜 버려?”라고 생각했는데, n이 100만쯤 되면 2n이든 3n이든 별 차이가 없고, n²이 붙는 순간 그게 전부를 지배하게 되니까 그런 거였습니다.
자주 보는 복잡도들
| Big O | 이름 | 예시 | 설명 |
|---|---|---|---|
| O(1) | 상수 시간 | 배열 인덱스 접근 | 입력 크기와 무관 |
| O(log n) | 로그 시간 | 이진 검색 | 입력 크기가 커져도 느리게 증가 |
| O(n) | 선형 시간 | 선형 검색 | 입력 크기에 비례 |
| O(n log n) | 선형로그 시간 | 퀵 정렬, 병합 정렬 | 대부분의 효율적인 정렬 |
| O(n²) | 제곱 시간 | 버블 정렬, 선택 정렬 | 중첩 반복문 |
| O(2ⁿ) | 지수 시간 | 피보나치(재귀) | 매우 비효율적 |
이걸 표로만 보면 감이 안 오는데, 직접 n=1000일 때 각각 몇 번 연산하는지 계산해보면 확 체감됩니다. O(n)은 1000번인데 O(n²)은 백만 번이고, O(2ⁿ)은… 그냥 안 됩니다.
코드로 보는 복잡도
이건 직접 코드에 대입해보면서 감을 잡은 부분입니다.
O(1) - 바로 접근
def get_first_element(arr):
return arr[0] # 항상 1번의 연산배열 길이가 10이든 10억이든, 첫 번째 원소 가져오는 건 한 번이면 끝납니다.
O(n) - for문 한 바퀴
def find_max(arr):
max_val = arr[0]
for num in arr: # n번 반복
if num > max_val: # 1번 비교
max_val = num
return max_val # 총 연산: O(n)반복문이 하나면 대체로 O(n)입니다.
O(n²) - for문 두 겹
def bubble_sort(arr):
for i in range(len(arr)): # n번
for j in range(len(arr)-1): # n번
if arr[j] > arr[j+1]: # 1번 비교
swap(arr, j, j+1) # 총 연산: O(n²)이중 반복문을 처음 보고 “이거 n이 좀만 커지면 느리겠다” 싶었는데, 실제로 n=10000만 돼도 체감될 정도로 느려집니다. 버블 정렬로 시간 초과 맞아본 게 이 때문이었습니다.
O(log n) - 반씩 줄어드는 탐색
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # 최대 log₂n번 반복
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1이진 탐색은 매번 탐색 범위가 절반으로 줄어들어서 O(log n)입니다. n이 백만이어도 약 20번이면 찾을 수 있다는 건데, 이걸 처음 알았을 때 좀 신기했습니다.
최선/최악/평균
같은 알고리즘이라도 운에 따라 빨리 끝날 수도, 끝까지 돌 수도 있습니다.
# 선형 검색의 경우 분석
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 최선 경우 (Best Case): O(1)
# - 찾는 값이 배열의 첫 번째에 있을 때
# 최악 경우 (Worst Case): O(n)
# - 찾는 값이 배열의 마지막에 있거나 없을 때
# 평균 경우 (Average Case): O(n/2) = O(n)
# - 모든 위치에 있을 확률이 같다고 가정보통 문제 풀 때는 최악 기준으로 생각합니다. 최선만 보고 “괜찮겠지” 하면 특정 케이스에서 터지니까요.
공간 복잡도
시간만 신경 쓰다가 메모리 초과를 처음 만났을 때 당황했던 기억이 있습니다. 공간 복잡도는 알고리즘이 추가로 얼마나 메모리를 쓰는지를 봅니다.
O(1) - 추가 메모리 거의 안 씀
def swap_sort(arr):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
arr[i], arr[j] = arr[j], arr[i] # 임시 변수만 사용
return arr
# 추가 공간: O(1) - 임시 변수만 사용원본 배열 안에서 자리만 바꾸니까, 배열이 아무리 커도 추가 메모리는 안 늘어납니다.
O(n) - 배열 하나 더 만듦
def copy_and_sort(arr):
copied = arr.copy() # O(n) 공간 추가
return sorted(copied)
# 추가 공간: O(n) - 배열 복사본 생성O(n²) - 2차원 배열
def create_multiplication_table(n):
table = [[0] * n for _ in range(n)] # n x n 크기의 2차원 배열
for i in range(n):
for j in range(n):
table[i][j] = (i+1) * (j+1)
return table
# 공간 복잡도: O(n²)n=10000이면 1억 개의 칸이 필요한 건데, 이 정도면 메모리 제한에 걸리기 쉽습니다.
재귀 함수에서의 복잡도
재귀는 시간이랑 공간을 둘 다 잡아먹을 수 있어서 주의가 필요합니다.
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
# 시간 복잡도: O(2ⁿ) - 지수 시간 (매우 비효율적)
# 공간 복잡도: O(n) - 콜 스택 깊이피보나치를 단순 재귀로 짜면 같은 값을 반복해서 계산합니다. fib(5)를 구하려고 fib(3)을 두 번, fib(2)를 세 번 구하는 식으로요. n=40만 돼도 눈에 띄게 느려지는 걸 보고 “아, 이래서 메모이제이션이 필요하구나” 싶었습니다.
def fibonacci_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
# 시간 복잡도: O(n) - 메모이제이션으로 최적화
# 공간 복잡도: O(n) - 메모 배열 + 콜 스택한 번 계산한 값을 저장해두면 O(2ⁿ)이 O(n)으로 떨어집니다. 같은 로직인데 딕셔너리 하나 추가한 것뿐인데 이렇게 차이가 나는 게 좀 충격이었습니다.
직접 시간 비교해보기
표로만 보면 와닿지 않아서, 실제로 O(n)이랑 O(n²)이 n이 커질 때 얼마나 차이 나는지 측정해본 코드입니다.
import time
import matplotlib.pyplot as plt
def measure_complexity():
sizes = [100, 500, 1000, 2000, 5000]
for n in sizes:
arr = list(range(n))
# O(n) 알고리즘
start = time.time()
linear_sum = sum(arr)
linear_time = time.time() - start
# O(n²) 알고리즘 (제곱 시간 예시)
start = time.time()
quadratic_sum = 0
for i in range(n):
for j in range(n):
quadratic_sum += 1
quadratic_time = time.time() - start
print(f"n={n}: O(n)={linear_time:.4f}s, O(n²)={quadratic_time:.4f}s")
measure_complexity()n=100일 때는 둘 다 순식간인데, n=5000쯤 되면 O(n²) 쪽이 확연하게 느려집니다. 이걸 직접 돌려보고 나서야 “아, 그래서 복잡도를 따지는 거구나” 하고 납득이 됐습니다.
입력 크기 보고 알고리즘 고르기
코딩 테스트에서 제일 실용적이었던 건 이 표입니다. 문제에서 n의 범위를 보고 어떤 복잡도까지 허용되는지 역산하는 건데, 이게 습관이 되면 접근법을 훨씬 빨리 정할 수 있습니다.
| 입력 크기 | 허용되는 복잡도 | 예시 알고리즘 |
|---|---|---|
| n ≤ 10 | O(n!) | 완전 탐색 |
| n ≤ 20 | O(2ⁿ) | 비트 마스크, DP |
| n ≤ 500 | O(n³) | 플로이드-워셜 |
| n ≤ 5000 | O(n²) | 동적 계획법 |
| n ≤ 10⁶ | O(n log n) | 정렬, 힙 |
| n ≤ 10⁹ | O(n) | 선형 탐색 |
| n > 10⁹ | O(log n), O(1) | 해시, 이진 검색 |
예를 들어 n이 10만이면 O(n²)은 100억이라 무조건 시간 초과입니다. 그러면 O(n log n) 이하로 풀어야 한다는 걸 문제 읽자마자 알 수 있습니다.
메모리 쪽도 비슷한 감각
- 보통 문제에서 메모리 제한이 256MB ~ 1GB 정도
- int 배열 1억 개가 대략 400MB쯤
- 2차원 배열 만들 때 n이 만 단위를 넘으면 한 번 계산해보는 게 좋음
- 시간을 줄이려고 메모리를 더 쓰는 트레이드오프는 자주 나옴 (메모이제이션이 대표적)
연습 문제
- 다음 코드의 시간 복잡도를 분석하세요:
def mystery_function(arr):
total = 0
for i in range(len(arr)):
for j in range(i, len(arr)):
total += arr[i] + arr[j]
return total-
다음 중 시간 복잡도가 가장 낮은 것은?
- A) O(1)
- B) O(log n)
- C) O(n)
- D) O(n²)
-
공간 복잡도가 O(1)인 정렬 알고리즘을 2개 이상 말해보세요.
-
피보나치 수열을 구하는 재귀 함수의 시간 복잡도를 분석하고, 이를 최적화하는 방법을 제안하세요.
정리하면서 느낀 것
복잡도 분석이 결국 하는 일은 “이 코드, n 커지면 괜찮을까?”에 대한 답을 주는 겁니다. 처음부터 정확하게 계산하려고 하면 오히려 어렵고, 반복문이 몇 겹인지, 재귀가 얼마나 퍼지는지, 추가 배열을 얼마나 만드는지 이 세 가지만 보는 습관부터 들이면 금방 감이 옵니다.