퀵정렬이 n log n이 되는 이유!

 출처 네이버블로그 > 공부는 자신의 인생을 바꾸는 드라마다.
http://blog.naver.com/newlogin_kr/140035838340

앞서 우스개 암기에서 보여드렸지만 퀵서비스맨의 앤은 자연을 사랑하는 앤이다. (n로브(그) n )

라고 했습니다.

어떻게 된걸까요?

정공법으로 쳐 봅시다.(만만하다는 사실은 이미 앞서 설명드렸으니 자신감 무장하시고)

책에 단 두줄로 이렇게 모든것을 표현햇습니다.

정확히 둘로 나누는 경우가 모든 경우에 발생한다면 둘로 나누고 난 것들의 2배의 시간과 반복되는 횟수2(T(n/2))를 평균치 세타로 바꿔서 단지 n번만 반복하므로 세타(n)이 나온다.

다시 말해보면

일단 절반으로 자른다.그러면 2개의 배열이 생성됨 각각은 n/2 길이

처음 길이가 n이고 처리 식의 시간을 세타(n)라고 하고 처리식은 t(n)이라고 할때

절반의 배열의 처리방식도 n의 처리방식과 동일하므로 처리상태는 t(n)=2*t(n/2)+2*세타(n/2)=2*t(n/2)+세타(n) 이 됩니다. 여기서 2*세타(n/2)인 이유는 배열의 길이가 반으로 줄은 대신에 처리할 개수가 2배 늘었기 때문이죠.

그렇다면 4조각이 될때는 t(n)=2^2*t(n/2^2)+세타(n)+2^2*세타(n/2^2)가 되는거죠

여기서 세타는 2번째 호출이기 때문에 t(n)을 두번째 처리하기 위해서 4등분한 조각에 4분의 1크기로 접근하는거죠 결국엔 n이 되니까 t(n)=2^2*t(n/2^2)+세타(2n)이 되는군요

이런 식으로 k번째 처리를 본다면

t(n)=2^k*t(n/2^k)+세타(kn) 이 나옵니다.

그렇다면 k를 n으로 소거해 보면 세타에 대한 명확한 답이 나올거 같은데

단서는 역시 마지막 한장(점화식에서 코너에 몰리면 이걸 꺼냅니다. )

t(1)=세타(1)=1

이 이미 주어져 있으므로

모든 k는 n에 만족해야 함으로

t(n/2^k)를 t(1)로 치환가능하고

1=n/2^k 은 항상 성립한다.

n=2^k

양쪽에 자연로그를 취하면(편의상 이진로그는 lo2라고 명칭합시다.)

ln n= ln 2^k

ln n= k* ln 2

ln n/ln 2 = k (앗싸 다풀었죠?)

다시 k를 n에 관한 식으로 치환하면

t(n)=2^(lo2  n) t(n/2^k)+세타(n *lo2 n)

=  n*t(1)+세타(n*lo2n) //2^lo2 n=n^lo2 2=n 이고 1=n/2^k는 항상 성립하므로

= n+세타 (n*lo2 n)

=n+세타(n*ln n/ln 2) //lo2 n=ln n/ln 2 이므로

n이상의 차수에서 상수배수 는 무시하므로 가장 높은 차수는 n*ln n 이 되고

세타(n*ln n) 이 성립한다.

추신)

점화식에서 제일 1순위는 t(1) 1항값인 상수값으로 바꾸는 것이고 그다음은 유도인자 k를 n에 대해 치환하는 것입니다