복잡도와 기초 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
빅오 표기
"""빅오 표기: 코드의 연산 수를 직접 세어 n에 따라 어떤 모양으로 느는지 확인한다.
시간: 함수마다 다르다 — 쌍 세기 O(n²), 두 배씩 늘리기 O(log n), 최댓값 찾기 O(n)
공간: O(1)
"""
import math
def count_pairs(n: int) -> int:
"""for i … for j in range(i + 1, n) 이중 반복문의 몸통 실행 횟수."""
count = 0
for i in range(n):
for _ in range(i + 1, n):
count += 1
return count
def count_doublings(n: int) -> int:
"""i = 1에서 시작해 i < n인 동안 i를 두 배로 하는 반복의 횟수."""
i = 1
steps = 0
while i < n:
i *= 2
steps += 1
return steps
def count_max_comparisons(values: list[int]) -> int:
"""최댓값을 찾으며 한 비교 횟수. 언제나 n - 1번이다."""
comparisons = 0
best = values[0]
for value in values[1:]:
comparisons += 1
if value > best:
best = value
return comparisons
def dominant_ratio(n: int) -> float:
"""3n² + 100n + 7에서 n² 항이 차지하는 비율. n이 클수록 1에 가깝다."""
total = 3 * n * n + 100 * n + 7
return 3 * n * n / total
if __name__ == "__main__":
assert count_pairs(5) == 10
assert count_pairs(6) == 15
for n in range(10):
assert count_pairs(n) == n * (n - 1) // 2
assert count_doublings(100) == 7
assert count_doublings(1) == 0
for n in (2, 10, 1000, 10**6):
assert count_doublings(n) == math.ceil(math.log2(n))
assert count_max_comparisons([7, 3, 9, 1]) == 3
assert count_max_comparisons([42]) == 0
# n = 10에서는 100n이 더 크지만, n이 커지면 n² 항이 거의 전부다
assert dominant_ratio(10) < 0.5
assert dominant_ratio(1000) > 0.96
print("ok")최선·평균·최악
"""최선·평균·최악: 선형 탐색과 삽입 정렬의 비교 횟수를 입력 모양별로 센다.
시간: 선형 탐색 최선 O(1), 평균·최악 O(n) / 삽입 정렬 최선 O(n), 평균·최악 O(n²)
공간: O(1)
"""
def linear_search_comparisons(values: list[int], target: int) -> int:
"""앞에서부터 target을 찾을 때까지 한 비교 횟수. 없으면 len(values)."""
for index, value in enumerate(values):
if value == target:
return index + 1
return len(values)
def average_hit_comparisons(values: list[int]) -> float:
"""배열의 값을 같은 확률로 찾을 때의 평균 비교 횟수 = (n + 1) / 2."""
total = sum(linear_search_comparisons(values, value) for value in values)
return total / len(values)
def insertion_sort_comparisons(values: list[int]) -> int:
"""values의 복사본을 삽입 정렬하며 한 비교 횟수."""
items = list(values)
comparisons = 0
for start in range(1, len(items)):
index = start
while index > 0:
comparisons += 1
if items[index - 1] <= items[index]:
break
items[index - 1], items[index] = items[index], items[index - 1]
index -= 1
return comparisons
if __name__ == "__main__":
data = [7, 3, 9, 1, 5, 8, 2, 6]
assert linear_search_comparisons(data, 7) == 1
assert linear_search_comparisons(data, 5) == 5
assert linear_search_comparisons(data, 4) == 8
assert linear_search_comparisons([], 1) == 0
assert average_hit_comparisons(data) == 4.5
# 찾는 값의 절반이 없는 값이면 평균이 바뀐다
assert 0.5 * average_hit_comparisons(data) + 0.5 * len(data) == 6.25
assert insertion_sort_comparisons([1, 2, 3, 4, 5]) == 4
assert insertion_sort_comparisons([5, 4, 3, 2, 1]) == 10
assert insertion_sort_comparisons(list(range(1000))) == 999
assert insertion_sort_comparisons(list(range(1000, 0, -1))) == 499_500
assert insertion_sort_comparisons([]) == 0
print("ok")분할 상환 분석
"""분할 상환 분석: 가득 차면 용량을 늘리는 동적 배열의 비용을 넣기마다 기록한다.
시간: 넣기 최악 O(n), 두 배씩 늘리면 분할 상환 O(1) / 일정 칸씩 더해 늘리면 분할 상환 O(n)
공간: O(n) — 두 배씩 늘리면 최대 절반 가까이가 빈 칸이다
"""
from typing import Callable
class DynamicArray:
"""용량을 grow 함수로 늘리는 동적 배열. 쓰기 1번과 옮긴 칸 1개를 비용 1로 센다."""
def __init__(
self,
capacity: int = 1,
grow: Callable[[int], int] = lambda capacity: capacity * 2,
) -> None:
self.capacity = capacity
self.grow = grow
self.slots: list = [None] * capacity
self.size = 0
self.costs: list[int] = []
def push(self, value) -> None:
"""끝에 value를 넣는다. 자리가 없으면 더 큰 배열로 모두 옮긴다."""
copied = 0
if self.size == self.capacity:
self.capacity = self.grow(self.capacity)
bigger = [None] * self.capacity
for index in range(self.size):
bigger[index] = self.slots[index]
copied += 1
self.slots = bigger
self.slots[self.size] = value
self.size += 1
self.costs.append(copied + 1)
def __getitem__(self, index: int):
if not 0 <= index < self.size:
raise IndexError(index)
return self.slots[index]
def fill(count: int, capacity: int, grow: Callable[[int], int] | None = None) -> DynamicArray:
"""1부터 count까지 넣은 동적 배열."""
array = DynamicArray(capacity) if grow is None else DynamicArray(capacity, grow)
for value in range(1, count + 1):
array.push(value)
return array
if __name__ == "__main__":
eight = fill(8, 1)
assert eight.costs == [1, 2, 3, 1, 5, 1, 1, 1]
assert sum(eight.costs) == 15
nine = fill(9, 2)
assert nine.capacity == 16
assert sum(nine.costs) == 23
doubling = fill(16, 2)
additive = fill(16, 2, lambda capacity: capacity + 2)
assert sum(doubling.costs) == 30
assert sum(additive.costs) == 72
# 두 배씩이면 몇 개를 넣어도 총비용이 3n을 넘지 않는다
for count in (1, 10, 100, 1000):
assert sum(fill(count, 1).costs) <= 3 * count
# 더해 늘리면 n이 열 배가 될 때 총비용은 열 배를 훨씬 넘는다(n²에 비례)
plus_two = lambda capacity: capacity + 2
assert sum(fill(1000, 2, plus_two).costs) > 50 * sum(fill(100, 2, plus_two).costs)
assert nine[8] == 9
try:
nine[9]
raise AssertionError("범위 밖 읽기는 IndexError여야 한다")
except IndexError:
pass
print("ok")메모리 계층과 캐시 지역성
"""메모리 계층과 캐시 지역성: 작은 캐시 모형으로 접근 순서별 캐시 미스를 센다(시간 측정 없이 결정적으로).
시간: 접근 하나에 O(캐시 라인 수) — 모형이라 단순하게 목록으로 둔다
공간: O(캐시 라인 수)
"""
import math
def count_misses(addresses: list[int], line_bytes: int, cache_lines: int) -> int:
"""주소 순서대로 읽을 때의 미스 수. 캐시는 라인 cache_lines개를 LRU로 기억한다."""
cache: list[int] = []
misses = 0
for address in addresses:
line = address // line_bytes
if line in cache:
# 적중: 가장 최근에 쓴 라인으로 옮긴다
cache.remove(line)
else:
misses += 1
if len(cache) == cache_lines:
cache.pop(0)
cache.append(line)
return misses
def matrix_addresses(size: int, element_bytes: int, row_major_walk: bool) -> list[int]:
"""행 우선으로 놓인 size×size 배열을 가로(True) 또는 세로(False)로 돌 때의 주소 순서."""
if row_major_walk:
cells = [(row, column) for row in range(size) for column in range(size)]
else:
cells = [(row, column) for column in range(size) for row in range(size)]
return [(row * size + column) * element_bytes for row, column in cells]
def lines_touched(total_bytes: int, line_bytes: int = 64) -> int:
"""이어진 total_bytes를 읽는 데 필요한 캐시 라인 수."""
return math.ceil(total_bytes / line_bytes)
if __name__ == "__main__":
# 4×4 정수(4바이트), 라인 16바이트 = 한 행
row_walk = matrix_addresses(4, 4, True)
column_walk = matrix_addresses(4, 4, False)
assert count_misses(row_walk, 16, 1) == 4
assert count_misses(column_walk, 16, 1) == 16
assert count_misses(column_walk, 16, 4) == 4
# 큰 배열(64×64)은 캐시보다 커서 세로로 돌면 거의 모두 미스다
big_rows = matrix_addresses(64, 4, True)
big_columns = matrix_addresses(64, 4, False)
assert count_misses(big_rows, 64, 8) == 64 * 64 // 16
assert count_misses(big_columns, 64, 8) == 64 * 64
# 흩어진 연결 리스트 노드 8개(16바이트)
nodes = [0, 704, 16, 720, 1408, 32, 736, 1424]
assert count_misses(nodes, 64, 1) == 8
assert count_misses(nodes, 64, 100) == 3
assert count_misses([index * 16 for index in range(8)], 64, 1) == 2
# 객체 1,000개: AoS(64바이트 객체)와 SoA(위치 12바이트만)
assert 1000 * lines_touched(64) == 1000
assert lines_touched(1000 * 12) == 188
assert count_misses([], 64, 1) == 0
print("ok")재귀와 호출 스택
"""재귀와 호출 스택: 팩토리얼의 스택 깊이, 피보나치의 호출 수와 메모이제이션을 센다.
시간: factorial O(n), 순진한 fib O(φⁿ) ≈ O(1.6ⁿ), 메모이제이션 fib O(n)
공간: 재귀 깊이만큼 O(n)의 호출 스택. 반복문 팩토리얼은 O(1)
"""
import sys
def factorial(n: int, depth: int = 1, deepest: list[int] | None = None) -> int:
"""n! 을 재귀로 구한다. deepest[0]에 도달한 가장 깊은 스택 깊이를 적는다."""
if deepest is not None:
deepest[0] = max(deepest[0], depth)
if n <= 1:
return 1
return n * factorial(n - 1, depth + 1, deepest)
def factorial_iterative(n: int) -> int:
"""같은 값을 반복문으로 구한다. 스택을 쌓지 않는다."""
result = 1
for value in range(2, n + 1):
result *= value
return result
def fib_naive(n: int, calls: list[int]) -> int:
"""정의 그대로의 재귀 피보나치. calls[0]에 호출 수를 센다."""
calls[0] += 1
if n < 2:
return n
return fib_naive(n - 1, calls) + fib_naive(n - 2, calls)
def fib_memo(n: int, memo: dict[int, int], calls: list[int]) -> int:
"""한 번 구한 답을 memo에 적어 두는 피보나치. calls[0]에 호출 수를 센다."""
calls[0] += 1
if n in memo:
return memo[n]
result = n if n < 2 else fib_memo(n - 1, memo, calls) + fib_memo(n - 2, memo, calls)
memo[n] = result
return result
def broken_fact(n: int) -> int:
"""바닥 조건이 없는 재귀. 끝나지 않고 스택 한도에서 RecursionError가 난다."""
return n * broken_fact(n - 1)
if __name__ == "__main__":
deepest = [0]
assert factorial(5, deepest=deepest) == 120
assert deepest[0] == 5
assert factorial(0) == 1
assert all(factorial(n) == factorial_iterative(n) for n in range(15))
calls = [0]
assert fib_naive(5, calls) == 5
assert calls[0] == 15
calls = [0]
fib_naive(20, calls)
assert calls[0] == 21891
calls = [0]
assert fib_memo(5, {}, calls) == 5
assert calls[0] == 9
calls = [0]
assert fib_memo(90, {}, calls) == 2880067194370816120
assert calls[0] == 2 * 90 - 1
try:
broken_fact(3)
raise AssertionError("바닥 조건이 없으면 끝나지 않아야 한다")
except RecursionError:
pass
# 반복문은 재귀 한도와 상관없다
assert factorial_iterative(sys.getrecursionlimit() * 2) > 0
print("ok")