퀵정렬 알고리즘의 시간복잡도

퀵 정렬 알고리즘의 시간 복잡도는    으로  알고 있습니다.

그런데 어떻게 해서 이렇게 나오는지 설명좀 해주셨으면 감사하겠습니다.

-----------------------------------------------------------------------

분할을 할 때 마다 평균적으로 1/10, 9/10의 두가지 경우로 쪼개진다고 가정을 해봅니다.

이는 평균적으로 일어나는 것 보다는 더 나쁜 경우를 생각한 것입니다.

n*(9/10)^k=1이 되는 k는 분할의 깊이가 됩니다.

양변에 로그를 취하면 log(n)+k(log(9)-log(10))=0이 됩니다.

간단하게 만들면 log(n)-ck=0 이 되고, k=log(n)/c 가 됩니다. c는 상수입니다.

즉 k=log2(n) 이 됩니다. 각 깊이마다 n씩 비용이 들기 때문에

전체적인 시간복잡도는 nlog2n 이 나오게 됩니다.

거의 대부분의 경우는 위의 분석대로 nlogn이 복잡도를 가지지만

최악의 경우에는 분할이 1; (n-2) 와 같은 방식으로 진행됩니다.

이 경우에는   시간복잡도가 n^2 이 된다고 하겠습니다.