지수와 로그: 빅데이터와 복잡도의 언어

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^10 = 1,024 ≈ 1K
2^20 = 1,048,576 ≈ 1M
2^30 ≈ 1B
2^32 ≈ 4.3B (32-bit 정수 한계)
2^64 ≈ 1.8 × 10^19 (64-bit 정수)

log₂(8) = 3   ← 2^3 = 8 이므로
log₂(1024) = 10
log₂(1000000) ≈ 20
log₁₀(1000) = 3
ln(e) = 1     ← 자연로그 (e ≈ 2.718)

import math

# 2^n
print(2 ** 10)   # 1024
print(pow(2, 20))  # 1048576

# log₂(n)
print(math.log2(1024))    # 10.0
print(math.log2(1000000)) # 약 19.93

# 자연로그
print(math.log(math.e))   # 1.0


# 지수 함수 시각화
import matplotlib.pyplot as plt
import numpy as np

x = np.linspace(0, 10, 100)
plt.plot(x, 2**x, label='2^x (지수 폭발)')
plt.plot(x, x**2, label='x² (다항식)')
plt.plot(x, x, label='x (선형)')
plt.plot(x[1:], np.log2(x[1:]), label='log₂(x) (로그)')
plt.legend()
plt.title('함수 성장 속도 비교')
plt.grid(True)
plt.show()
# → 지수는 빠르게 폭발, 로그는 거의 평평

# O(n)   — 선형 탐색: 1000개 데이터 → 1000번 비교
# O(log n) — 이진 탐색: 1000개 데이터 → 약 10번 비교

import time


def linear_search(arr, target):
    """O(n) — 처음부터 끝까지"""
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1


def binary_search(arr, target):
    """O(log n) — 정렬된 배열에서 절반씩 줄이기"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


# 100만 개에서 999,999 찾기
arr = list(range(1_000_000))

t0 = time.perf_counter()
linear_search(arr, 999_999)
t_linear = time.perf_counter() - t0

t0 = time.perf_counter()
binary_search(arr, 999_999)
t_binary = time.perf_counter() - t0

print(f"선형 탐색: {t_linear*1000:.2f}ms")  # ~30ms
print(f"이진 탐색: {t_binary*1000:.2f}ms")  # ~0.005ms
print(f"속도 차이: {t_linear / t_binary:.0f}배")  # ~6000배

# log₂(1,000,000) ≈ 20
# 선형은 1,000,000 비교 vs 이진은 20 비교 → 50,000배 빠름

def complexity_table(n_values=[10, 100, 1000, 10000, 100000, 1000000]):
    print(f"{'N':>10} {'O(1)':>8} {'O(log n)':>10} {'O(n)':>10} {'O(n log n)':>14} {'O(n²)':>14}")
    for n in n_values:
        log_n = math.log2(n)
        print(f"{n:>10,} {1:>8} {log_n:>10.1f} {n:>10,} {n*log_n:>14,.0f} {n*n:>14,}")


complexity_table()
# 결과:
#         N    O(1)  O(log n)      O(n)     O(n log n)         O(n²)
#        10       1       3.3        10             33           100
#       100       1       6.6       100            664        10,000
#     1,000       1       10.0     1,000          9,966     1,000,000
#    10,000       1       13.3    10,000        132,877   100,000,000
#   100,000       1       16.6   100,000      1,660,964 10,000,000,000
# 1,000,000       1       19.9  1,000,000      19,931,569 1,000,000,000,000

# 1초에 1억 번 연산 가능한 컴퓨터에서 N=1,000,000 처리 시:

operations_per_second = 100_000_000

scenarios = {
    'O(log n)':    20,
    'O(n)':        1_000_000,
    'O(n log n)':  20_000_000,
    'O(n²)':       1_000_000_000_000,
    'O(2^n) when n=30': 2**30,
}

for name, ops in scenarios.items():
    seconds = ops / operations_per_second
    if seconds < 1:
        print(f"{name:30} {seconds*1000:.3f}ms")
    elif seconds < 60:
        print(f"{name:30} {seconds:.1f}초")
    elif seconds < 3600:
        print(f"{name:30} {seconds/60:.1f}분")
    elif seconds < 86400:
        print(f"{name:30} {seconds/3600:.1f}시간")
    else:
        print(f"{name:30} {seconds/86400:.0f}일")