java復雜度

A. 快速排序的演算法復雜度分析

原文地址：
快速排序的演算法復雜度分析
以下是快排的java演算法：

大家都知道快排的時間復雜度是O(n*ln[n])，那麼這個復雜度是如何計算出來的呢？

最好的情況下，每次劃分對一個記錄定位後，要記錄的左側子序列與右側子序列的長度相同。在具有n個記錄的序列中，一次劃分需要對整個待劃分序列掃描一遍，所需的時間為O(n)。

設 是對n個記錄的序列進行排序的時間，每次劃分後，正好把劃分區域分為長度相等的連個子序列，顯然T(0)=T(1) =1,則有：

最壞的情況下，待排序的記錄序列正序或逆序，每次劃分只能得到一個比上一次劃分少一個記錄的子序列，（另一個子序列為空）。此時，必須經過n-1次遞歸調用才能把所有記錄定位，而且第i趟劃分需要經過n-i次比較才能找個才能找到第i個記錄的位置，因此時間復雜度為

平均情況下，設軸值記錄的關鍵碼第k小（1≤k≤n）,則有：

由上式可推出如下兩式：

兩式相減,然後兩邊同除以n(n+1)得

又因為f(n)單調遞減，單調有界數列極限定理，所以f(n)有界

此數稱為歐拉常數，

約為 0.57721566490153286060651209

所以

所以

**如果有何處不當，請不吝賜教，一定多加完善。謝謝 **

參考資料：

【1】《演算法設計與分析》第二版 王紅梅