溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、隨機化快速排序算法
(1)、快速排序的壞處：完全順序/完全逆序時時間復雜度為：O(n^2)，其余的情況時間復雜度為：O(nlogn),算法的效率與輸入順序有關；
(2)、隨機選擇主元，好處：其運行時間不依賴于輸入序列的順序，算法的效率與輸入的順序無關；
(3)、最差的情況由隨機數產生器決定，隨機化快速排序的時間復雜度為：O(nlogn)；
2、比較排序的算法模型
該模型中，只能做的操作：< <= > .......，來決定元素的相對順序；
局限性：該模型只能用于可以比較大小的數據類型；
總結：比較排序的算法時間復雜度不會小于：O(nlogn);
3、決策樹下的排序算法
有3個數<a1, a2, a3>，用決策樹進行排序。
(1)、決策樹：一般情況下，有n個元素需要排序，左邊的子樹說明ai <= aj；右邊的子樹對應ai > aj；每一個葉子結點表示一種排序結果，最終的結果a1 < a2 < a3......< an；
(2)、因此比較型排序算法都可以被轉換成決策樹模型的方式；
(3)、n值的決策樹，就是把算法中這些比較的所有可能結果分別列出來；決策樹指出了所有可能的路線，用決策樹分析比較型的算法是很有用的；
對于n個元素的排序， 用決策樹可以證明比較型的排序算法的時間復雜度：取決于樹的高度，此時葉子節點的個數是n!，樹高>=nlog(n);
樹的高度決定比較的次數，進而決定時間復雜度；
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
