當前位置:首頁 » 編程語言 » java復雜度

java復雜度

發布時間: 2024-04-03 06:54:14

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】《演算法設計與分析》第二版 王紅梅

熱點內容
java怎麼裝 發布:2025-04-03 12:41:54 瀏覽:847
伺服器和路由器屬於什麼設備 發布:2025-04-03 12:25:43 瀏覽:873
新手學java7編程 發布:2025-04-03 12:17:27 瀏覽:871
某寶演算法 發布:2025-04-03 12:12:26 瀏覽:284
腳本模擬滑鼠點擊 發布:2025-04-03 12:06:19 瀏覽:317
老安卓介面是什麼 發布:2025-04-03 11:57:31 瀏覽:762
nginx資源伺服器搭建 發布:2025-04-03 11:44:52 瀏覽:406
安卓開發和嵌入式哪個難 發布:2025-04-03 11:25:09 瀏覽:318
ftp鏈接本地虛擬機 發布:2025-04-03 11:25:02 瀏覽:793
手機扣扣怎麼找回密碼 發布:2025-04-03 11:24:17 瀏覽:223