빅오 표기법: 코드 속도의 수학

O(1)        상수
O(log n)    로그 (이진 탐색)
O(n)        선형 (단순 루프)
O(n log n)  머지/퀵 정렬
O(n²)       이중 루프
O(n³)       삼중 루프
O(2^n)      재귀 피보나치 (메모 X)
O(n!)       순열 모두 시도

import math
import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 30, 100)

plt.figure(figsize=(10, 6))
plt.plot(n, np.ones_like(n),       label='O(1)')
plt.plot(n[1:], np.log2(n[1:]),    label='O(log n)')
plt.plot(n, n,                      label='O(n)')
plt.plot(n[1:], n[1:] * np.log2(n[1:]), label='O(n log n)')
plt.plot(n, n ** 2,                 label='O(n²)')
plt.plot(n, 2 ** n,                 label='O(2^n)')
plt.ylim(0, 1000)
plt.xlabel('N (입력 크기)')
plt.ylabel('연산 횟수')
plt.legend()
plt.grid(True)
plt.title('Big-O 성장률 비교')
plt.show()
# O(2^n)이 가장 빠르게 폭발

# 1초에 1억 연산 가능 가정

def estimate_time(complexity, n):
    operations = {
        'O(1)': lambda x: 1,
        'O(log n)': lambda x: math.log2(x) if x > 0 else 0,
        'O(n)': lambda x: x,
        'O(n log n)': lambda x: x * math.log2(x) if x > 0 else 0,
        'O(n²)': lambda x: x * x,
        'O(2^n)': lambda x: 2 ** min(x, 60),  # 큰 수 방지
    }[complexity](n)
    seconds = operations / 100_000_000
    if seconds < 1: return f"{seconds*1000:.2f}ms"
    if seconds < 60: return f"{seconds:.1f}초"
    if seconds < 3600: return f"{seconds/60:.1f}분"
    if seconds < 86400: return f"{seconds/3600:.1f}시간"
    return f"{seconds/86400:.0f}일"


print(f"{'N':>10} {'O(n)':>10} {'O(n log n)':>15} {'O(n²)':>15} {'O(2^n)':>15}")
for n in [10, 100, 1_000, 10_000, 100_000, 1_000_000]:
    print(f"{n:>10,} {estimate_time('O(n)', n):>10} "
          f"{estimate_time('O(n log n)', n):>15} "
          f"{estimate_time('O(n²)', n):>15} "
          f"{estimate_time('O(2^n)', min(n, 30)):>15}")

# 결과:
# N=100,000일 때 O(n²) = 100억 = 100초+
# N=30일 때 O(2^n) = 10초+

import time

def measure(fn, *args):
    t0 = time.perf_counter()
    fn(*args)
    return time.perf_counter() - t0


# O(n) — 단일 루프
def linear(arr):
    return sum(arr)

# O(n²) — 중첩 루프
def quadratic(arr):
    pairs = []
    for i in arr:
        for j in arr:
            pairs.append((i, j))
    return pairs

# O(n log n) — 정렬
def n_log_n(arr):
    return sorted(arr)


# 데이터 크기별 시간 비교
for size in [100, 1000, 10_000]:
    arr = list(range(size))
    t1 = measure(linear, arr)
    t2 = measure(quadratic, arr)
    t3 = measure(n_log_n, arr)
    print(f"N={size:>6} | O(n): {t1*1000:.3f}ms | O(n²): {t2*1000:.3f}ms | O(n log n): {t3*1000:.3f}ms")

# 패턴 1: 단일 루프 → O(n)
def find_max(arr):
    m = arr[0]
    for x in arr[1:]:
        if x > m:
            m = x
    return m


# 패턴 2: 중첩 루프 → O(n²)
def has_duplicates_v1(arr):
    for i, a in enumerate(arr):
        for j, b in enumerate(arr):
            if i != j and a == b:
                return True
    return False


# 패턴 2 개선: O(n) — 해시셋
def has_duplicates_v2(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False


# 패턴 3: 절반씩 줄이기 → O(log n)
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


# 패턴 4: 분할 정복 → O(n log n)
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(a, b):
    result = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    return result + a[i:] + b[j:]

빠른정렬 (Quicksort):
- 최선: O(n log n) — 균등 분할
- 평균: O(n log n)
- 최악: O(n²) — 이미 정렬된 입력

해시 검색:
- 평균: O(1)
- 최악: O(n) — 모든 키가 한 버킷

→ Big-O는 보통 최악을 의미. 실전은 평균도 봐야 함.