최선, 최악, & 평균 경우
알고리즘을 측정하는 세 가지 방법
모든 알고리즘의 비용은 입력에 따라 다릅니다. 동일한 크기의 두 입력이 매우 다른 실행 시간을 생성할 수 있습니다. 복잡도 분석은 그 변동에 대한 세 가지 관점을 형식화합니다.
최선 경우 — Ω (오메가): 알고리즘이 가장 빠르게 끝나도록 하는 입력입니다. N개 항목 목록에서 선형 검색의 경우: Ω(1) — 대상이 첫 번째 위치를 차지합니다. 한 번의 비교, 완료.
최악 경우 — O (빅 오): 알고리즘이 가장 느리게 끝나도록 하는 입력입니다. 선형 검색의 경우: O(N) — 대상이 목록의 마지막에 있거나 전혀 나타나지 않습니다. 모든 요소를 검사해야 합니다.
평균 경우 — Θ (세타): 균등 분포를 가정하여 모든 가능한 입력에 대한 예상 비용입니다. 대상이 N개 위치 중 어디든 같은 확률로 나타날 수 있는 선형 검색의 경우: Θ(N/2) = Θ(N). 상수 1/2는 세타가 타이트한 점근적 성장을 나타내고 정확한 계수는 나타내지 않기 때문에 제거됩니다.
최악 경우가 지배하는 이유
시스템은 최악 경우를 처리해야 합니다. 평균 10ms이지만 때때로 60초가 걸리는 데이터베이스 쿼리는 사용자에게 보이는 실패를 야기합니다. 엔지니어는 입력에 관계없이 성능이 예측 가능하도록 최악의 경우 경계를 위해 설계합니다. 평균 경우 분석은 확률적 설정에서 가치가 있지만, 최악 경우 분석은 보장을 제공합니다.
이진 검색 경우 분석
이진 검색은 정렬된 배열에서만 작동합니다. 각 단계에서: 대상을 중점의 요소와 비교합니다. 대상이 중점과 같으면 반환합니다. 대상이 더 작으면 왼쪽 절반에서 재귀합니다. 더 크면 오른쪽 절반에서 재귀합니다.
각 비교는 남은 후보의 절반을 제거합니다.
메모리 성장 & 시간-공간 상충
작업이 아닌 메모리 세기
시간 복잡도는 알고리즘이 실행하는 작업 수를 측정합니다. 공간 복잡도는 입력을 초과하여 할당하는 추가 메모리를 측정합니다. 둘 다 프로덕션 시스템에서 중요합니다: 빠른 알고리즘이 O(N²) 메모리를 할당하면 서버가 소진됩니다.
O(1) 공간: N에 관계없이 일정한 추가 메모리입니다. 제자리 정렬(예: 삽입 정렬)은 원래 배열 내에서 요소를 교환합니다. 소수의 임시 변수만 사용합니다 — 배열이 얼마나 크든 O(1)입니다.
O(N) 공간: 입력 크기에 비례하는 메모리입니다. N개 요소 배열의 사본을 만들려면 N개 슬롯이 필요합니다. N개의 문자열 목록에서 해시 세트를 구축하면 최대 N개 항목을 저장합니다.
O(N²) 공간: N²에 비례하는 메모리입니다. N개 정점이 있는 그래프에 대한 N×N 인접 행렬을 구축하려면 N² 셀이 필요합니다. N = 10,000개 정점에서 이는 10^8개 항목 — 간단한 부울 그리드에 대해 수백 메가바이트입니다.
시간-공간 상충
알고리즘 설계의 기본적인 이동 중 하나: 공간과 시간을 거래하거나 시간과 공간을 거래합니다.
해시 테이블은 O(N) 추가 공간을 사용하여 O(1) 조회를 달성합니다. 해시 테이블이 없으면 목록 스캔이 O(N) 조회를 O(1) 추가 공간으로 달성합니다. 해시 테이블은 메모리를 지불하여 속도를 구입합니다.
메모이제이션은 이전에 계산된 결과를 저장합니다(O(N) 이상의 공간) 재계산을 피합니다. 메모이제이션 없는 재귀 피보나치는 O(2^N) 시간에 실행됩니다. 메모이제이션 사용: O(N) 시간 및 O(N) 공간. 공간 투자는 시간을 지수적으로 축소합니다.
해시 사전 vs 정렬된 목록
단어 발생 수를 세는 두 가지 전략을 비교하세요 N개 단어의 문서에서:
전략 A: 사전(해시 맵). 각 단어를 삽입; 그 개수를 증가시킵니다.
전략 B: 본 단어의 정렬된 목록을 유지합니다; 삽입하기 전에 멤버십을 확인하려면 이진 검색을 사용합니다.
분할 상환 분석: 비용 분산
가끔의 비용이 평균 성능을 망치지 않을 때
일부 작업은 가끔 비싸지만 시퀀스 전체에서 평균적으로 저렴합니다. 분할 상환 분석은 전체 시퀀스에 대해 작업당 평균 비용을 계산합니다 — 단일 작업의 최악의 경우 비용이 아닙니다.
동적 배열(Python 목록, Java ArrayList): 용량 1로 시작합니다. 가득 차면 용량을 두 배로 늘립니다. 두 배로 늘리면 모든 기존 요소를 복사합니다: 한 번의 추가를 위해 O(N) 작업. 하지만 두 배로 늘리기는 드뭅니다. N개 총 추가 후, 총 몇 개의 복사 작업이 발생했습니까?
두 배로 늘리기는 크기 1, 2, 4, 8, ..., N/2에서 발생합니다. 복사 횟수: 1 + 2 + 4 + ... + N/2. 이는 모든 N번 추가에서 총 N − 1 복사로 합산되는 기하급수입니다. 추가당 평균 복사: (N − 1) / N < 1, 따라서 추가당 O(1) 분할 상환 두 배로 늘릴 때마다 O(N) 최악의 경우 비용에도 불구하고.
분할 상환 분석이 중요한 이유
가끔 구조를 크기 조정, 재조정 또는 압축하기 위해 일시 중지되는 시스템은 경보할 만한 최악의 경우 개별 작업을 가지고 있는 것처럼 보일 수 있습니다. 분할 상환 분석은 경보가 거짓임을 드러냅니다: 드문 비싼 이벤트는 많은 저렴한 이벤트로 지불됩니다. 분할 상환 비용을 이해하면 과다 엔지니어링을 방지합니다: 분할 상환에 O(1)만 기여하는 드문 O(N) 작업을 피하기 위해 복잡성을 추가하는 것은 낭비된 작업입니다.
더 깊이 있게: unhamming 과정은 복잡도 분석을 프로덕션 소프트웨어의 실제 결함에 적용합니다. 누락된 장: 알고리즘 복잡도 & MOAD-0001: 퇴적 결함을 참조하세요.
해시 테이블 분할 상환 삽입
해시 테이블은 비어 시작하고 로드 계수가 0.75를 초과할 때마다 용량을 두 배로 늘립니다. 1,000개 요소를 삽입하면 정확히 10번 두 배로 늘리기가 용량 1, 2, 4, 8, 16, 32, 64, 128, 256, 512에서 트리거됩니다.