導航:首頁 > 源碼編譯 > 快速排序演算法的時間復雜度分析

快速排序演算法的時間復雜度分析

發布時間:2024-10-06 22:07:19

❶ 快速排序的時間復雜度

快排的平均時間為:T(n) = k*n*lnn
時間復雜度為:O(n*logn)

❷ 快速排序演算法在平均情況下的時間復雜度為 求詳解

時間復雜度為O(nlogn) n為元素個數
1. 快速排序的三個步驟:
1.1. 找到序列中用於劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分後的兩個序列重復1,2兩個步驟指導序列無法再劃分
所以對於n個元素其排序時間為
T(n) = 2*T(n/2) + n (表示將長度為n的序列劃分為兩個子序列,每個子序列需要T(n/2)
的時間,而劃分序列需要n的時間)
而 T(1) = 1 (表示長度為1的序列無法劃分子序列,只需要1的時間即可)
T(n) = 2^logn + logn * n (n被不斷二分最終只能二分logn次(最優的情況,每次選取
的元素都均分序列))
= n + nlogn
因此T(n) = O(nlogn)
以上是最優情況的推導,因此快速排序在最優情況下其排序時間為O(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為冒泡排序,T(n) = T(n - 1) + n (每次選取的元素只能將序列劃分為
一段,即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相當於O(n^2)

❸ 快速排序法的平均時間復雜度是多少

快速排序法的時間復雜度是nlogn(n×log以2為底n的對數)

拓展:

快速排序(Quicksort)是對冒泡排序的一種改進。

快速排序由C. A. R.
Hoare在1962年提出。它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

附各種排序法的時間復雜度如下:

閱讀全文

與快速排序演算法的時間復雜度分析相關的資料

熱點內容
python列表倒置 瀏覽:606
陰線埋伏指標源碼 瀏覽:126
定時休眠命令 瀏覽:743
航海王熱血伺服器為什麼是灰色的 瀏覽:113
不在域內的伺服器如何與域用戶共享文件夾 瀏覽:24
轉轉app裡面有什麼 瀏覽:980
玄學魏晉pdf 瀏覽:642
程序員面試有幫助嗎 瀏覽:148
平板怎麼使用安卓系統 瀏覽:573
程序員慘 瀏覽:772
直接生成頁面貼入源碼js不執行 瀏覽:491
嗨嗨直播app怎麼直播 瀏覽:87
卻連接不了伺服器怎麼搞 瀏覽:87
老別克壓縮機 瀏覽:582
如何查找軟體的加密數據文件 瀏覽:978
程序員同學級別 瀏覽:81
手機加密視頻播放不了 瀏覽:650
單片機點燈照片 瀏覽:705
軟體伺服器離線怎麼解決 瀏覽:457
應用隱私加密怎麼關 瀏覽:629