복잡도 하한·비교 정렬·Decision Tree

한 알고리즘의 분석에서 모든 알고리즘의 한계로

Insertion sort의 최악 비교 수를 계산하는 것은 특정 알고리즘의 상한 분석입니다. 비교만 허용하는 모든 정렬 방법이 일정 수 이상의 비교를 해야 함을 보이는 것은 계산 모형의 하한입니다. 두 주장은 양화하는 대상이 다릅니다. 현재 n=2부터 7까지 서로 다른 key의 모든 순열을 실제로 insertion sort 또는 mergesort로 정렬하고 비교 outcome trace를 남깁니다.

파랑은 균일 순열 분포에서 실제 비교 수의 정확한 PMF이며 주황은 선택한 순열의 항입니다. Query index는 n!로 나눈 나머지입니다. n을 바꾸어도 기존 index를 사용할 수 있지만 같은 입력 순열이라는 뜻은 아닙니다.

Decision Tree의 잎과 깊이

각 비교는 binary 결과를 주고, 그 결과에 따라 다음 비교나 반환하는 index 순서가 달라집니다. 서로 다른 n!개의 상대 순서를 구별해야 하므로 최소 n!개의 잎이 필요합니다. 여기서 구별하는 것은 출력 key 값들의 집합이 아니라 입력 원소들을 어느 순서로 배치해야 하는지입니다.

이는 결정론적 comparison sorting의 최악 깊이 하한입니다. n!≥(n/2)^{n/2}를 쓰면 Omega(n log n)을 얻습니다. 어떤 입력 하나가 빠르다는 사실은 이 하한과 모순되지 않습니다. 평균 깊이의 정보 하한 log₂(n!)와 최악 깊이에 적용한 ceiling도 구분하세요.

실제 비교를 세는 방법

Insertion sort는 key를 앞쪽으로 이동시키며 key 비교가 발생할 때마다 한 번 셉니다. 배열 index 확인이나 loop 분기는 제외합니다. Mergesort는 두 정렬된 절반의 맨 앞 key를 비교할 때만 셉니다. 진단 trace 저장과 모든 순열 생성 비용도 이 알고리즘 비교 수와 별개입니다.

서로 다른 순열에서 나온 trace 수가 n!인지, 실제 정렬 결과가 오름차순인지, 관측 최악이 counting 하한 이상인지 검산합니다. 이 전수 실험은 작은 n의 구현 근거입니다. 일반 lower bound 자체는 위의 잎 수 논증에서 나옵니다.

손계산과 직접 풀기

n=3이면 순열은 6개이고 ceil(log₂6)=3입니다. Insertion sort는 이미 정렬된 입력에서 2회, 역순에서 3회입니다. 최악 하한이 3이라는 것은 모든 입력이 3회여야 한다는 뜻이 아닙니다. n=5 mergesort의 관측 최악은 8이고 counting 하한은 7입니다. 낮은 하한이 항상 달성 가능하다는 보장도 없습니다.

직접 풀기: n=7에서 counting 하한과 현재 mergesort의 최악을 비교하세요. 풀이: 7!=5040이므로 ceil(log₂5040)=13입니다. 균형 분할 mergesort의 최악 n ceil(log₂n)-2^{ceil(log₂n)}+1은 21-8+1=14입니다. 화면의 5040개 실제 trace로 이 유한 결과를 확인할 수 있습니다.

모형을 넘어서 일반화하지 않기

정수 표현을 사용하는 counting·radix 정렬은 비교만 허용한 모형이 아닙니다. Key 범위와 word 길이, 사용 메모리의 가정을 따로 분석해야 합니다. 같은 하한을 모든 계산에 그대로 적용하면 안 됩니다. 또한 정렬의 comparison 하한은 P와 NP 관계를 결정하는 논증이 아닙니다.

AI가 알고리즘을 제안할 때 성공한 작은 예시, 모든 입력의 정확성, 특정 계산 모형의 상한과 하한을 구분하세요. 하한은 실험에서 느렸다는 관측이 아니라 허용된 모든 알고리즘에 대한 논증입니다.

참고: MIT 알고리즘 자료.