모든 복잡도 클래스는 곡선을 그립니다
입력 크기에 따른 비용 그래프
x축에 입력 크기 N을, y축에 비용(연산, 시간)을 놓으세요. 각 복잡도 클래스는 고유한 곡선을 생성합니다. 알고리즘의 성장률을 성능 곡선의 형태로 인식할 수 있습니다.
O(1) — 평평한 수평선. 함수 f(N) = 1. 기울기가 없습니다. N에 관계없이 비용은 절대 변하지 않습니다. 해시 테이블 조회: 테이블이 10개 또는 10,000,000개의 요소를 포함하든, 한 번의 해시 계산이 올바른 버킷으로 이동합니다.
O(log N) — 부드러운 상향 곡선, 감소하는 기울기. N = 1,000,000일 때: 비용 ≈ 20개 연산. 곡선은 작은 N에서 가파르게 상승하다가 평평해집니다. N이 두 배가 될 때마다 정확히 1개 단위의 비용이 추가됩니다.
O(N) — 대각선 직선. 기울기 = 1(점근적 의미에서). 비용은 N과 같은 속도로 증가합니다. N이 3배가 되면 비용도 3배가 됩니다.
O(N log N) — 완만한 상향 곡률을 가진 더 가파른 대각선. O(N) 위에 있지만 O(N²) 아래에 있습니다. 로그 인수는 선형 기울기에 천천히 증가하는 배수를 추가합니다.
O(N²) — 위로 열린 포물선. N이 증가함에 따라 기울기가 증가합니다. N = 10일 때: 비용 = 100. N = 100일 때: 비용 = 10,000. N = 1,000일 때: 비용 = 1,000,000.
커지는 간격
O(N²) / O(N) = N의 비율입니다. 포물선과 대각선 사이의 간격은 N이 증가함에 따라 커집니다. N = 10일 때: 10배 간격. N = 100일 때: 100배 간격. N = 1,000일 때: 1,000배 간격. N = 50,000일 때: 50,000배 간격. 간격은 항상 N과 같습니다.
규모 간격 계산
큰 의존성 그래프에 50,000개의 패키지가 포함되어 있습니다(N = 50,000). 한 알고리즘은 O(N) 시간에 실행됩니다. 다른 하나는 O(N²)에서 실행됩니다. 이 N에서 비율 O(N²)/O(N) = N = 50,000입니다.
선분 이등분
반복 이등분으로서의 이진 탐색
N개 요소의 정렬된 배열은 길이가 N인 선분을 형성합니다. 이진 탐색은 이 선분을 반복적으로 이등분합니다:
1. 남은 선분의 중점을 가리킵니다.
2. target < midpoint인 경우: 오른쪽 절반이 사라집니다. 왼쪽 절반에서 재귀합니다.
3. target > midpoint인 경우: 왼쪽 절반이 사라집니다. 오른쪽 절반에서 재귀합니다.
4. target = midpoint인 경우: 완료.
k번의 이등분 후, 남은 선분의 길이는 N / 2^k입니다. 그 길이가 1과 같을 때 탐색이 끝납니다:
N / 2^k = 1 → 2^k = N → k = log₂N
따라서 N개 요소에 대한 이진 탐색은 최대 log₂N개의 비교가 필요합니다.
이등분 & 두 배: 같은 곡선의 두 측면
이등분과 두 배는 기하학적 역함수입니다. 지수 곡선 2^k와 로그 곡선 log₂N은 직선 y = x를 기준으로 서로 반사됩니다.
종이 접기를 생각해보세요: 시작할 때 두께가 0.1mm입니다. 각 접기마다 두께가 두 배가 됩니다. 42번 접기 후: 0.1mm × 2^42 ≈ 439,804km — 달을 지나갑니다(384,400km). 이진 탐색은 역을 실행합니다: N개 요소로 시작하여, 각 단계마다 개수를 이등분하여, log₂N 단계에서 1개 요소에 도달합니다.
기하학적으로: 이등분은 자기 유사 연산입니다. 각 이등분은 전체와 구조적으로 동일하게 보이는 두 개의 절반을 생성합니다. 재귀와 로그는 이 자기 유사성을 공유합니다.
비교 & 두 배
정렬된 배열에 1,048,576개의 요소가 있습니다. 참고: 1,048,576 = 2^20.
기하학적 맵으로서의 해시 함수
함수로서의 해시 함수
해시 테이블은 해시 함수를 사용하여 키를 버킷에 매핑합니다:
bucket = hash(key) mod table_size
이는 엄격한 수학적 의미의 함수입니다: 정의역(모든 가능한 키)을 치역(버킷 인덱스 0에서 table_size - 1)으로 매핑합니다. 기하학적 그림: 키는 한 공간을 차지하고, 버킷은 다른 공간을 차지합니다. 해시 함수는 키를 버킷 인덱스로 투영합니다.
O(1) 조회 — 직접 이동, 검색 없음. 해시 함수는 일정한 시간에 버킷 인덱스를 계산합니다. 해당 버킷으로 직접 이동합니다. 순회 없음, 비교 루프 없음.
로드 인수. 로드 인수가 0.75일 때 버킷의 75%에 최소한 하나의 요소가 포함됩니다. ~0.9 이상에서 충돌이 증가합니다: 두 키가 같은 버킷으로 해시되어 그 버킷 내에 요소 체인을 형성합니다. 긴 체인에서의 조회는 최악의 경우 O(N)으로 저하됩니다.
기하학으로서의 분포 품질
잘 분포된 해시 함수는 키를 모든 버킷에 균일하게 분산시킵니다. 기하학적으로: 함수의 치역이 여치역을 균등하게 커버합니다. 모든 버킷은 약 N / table_size개의 키를 받습니다.
좋지 않은 해시 함수는 키를 몇 개의 버킷으로 클러스터합니다. 기하학적으로: 함수의 치역이 여치역의 부분 집합으로 축소됩니다 — 대부분의 키가 같은 몇 점으로 매핑됩니다. 나머지 버킷은 비어있습니다.
MOAD-0001과의 연결
리스트를 세트로 바꾸면 MOAD-0001을 수정합니다. 세트가 내부적으로 해시 테이블을 사용하기 때문입니다. O(N) 리스트 스캔 → O(1) 해시 테이블 조회. 기하학적으로: 수열을 따라 선형 순회가 함수를 통한 직접 투영으로 변환됩니다. 수열은 사라집니다; 함수가 이를 대체합니다.
분포가 좋지 않은 해시 분석
해시 테이블에 1,000개의 버킷과 900개의 요소가 있습니다(로드 인수 0.9). 좋지 않은 해시 함수가 이 요소 중 500개를 같은 버킷으로 보냅니다.