選擇算法
此條目需要擴充。 (2017年4月13日) |
在計算機科學中,選擇算法是一種在列表或數組中找到第k個最小數字的算法;這樣的數字被稱為第k個順序統計量。該算法尋找的對象主要有三種:最小、最大和中位數。已知存在O(n)(最壞情況下為線性時間)的選擇算法,還有對於結構化數據可能有次線性的表現的算法;在極端的情況下,對於已排序數據是O(1)。選擇是一些更複雜問題的子問題,如最近鄰和最短路徑問題。 許多選擇算法是由排序算法推廣而來,反之,一些排序算法可由反覆應用選擇算法推導出來。
最簡單的選擇算法是通過遍歷列表找到最小(或最大)的元素,在此過程中跟蹤當前的最小(或最大)值。這種算法與選擇排序有關。相反地,最困難的選擇算法是尋找中位數,這必然需要n/2的空間。 事實上,一個專門的中位選擇算法可用來構造一個一般選擇算法,例如中位數的中位數。已知最好的選擇算法是快速選擇(quickselect),它與快速排序有關。和快速排序類似,它有漸進最佳的複雜度,但是最壞情況的複雜度較差。不過這可以通過調整基準(pivot)的選擇來優化。
通過排序選擇
[編輯]通過對列表或數組的排序,然後選擇所需的元素,選擇算法可以規約為排序算法。這種方法對於選擇單個元素是低效的,但需要從數組中做出很多選擇時是高效的。在這種情況下,僅僅需要一個起初一個代價昂貴的排序,緊接着就是各種便宜的選擇操作了 – 對於數組而言是 O(1)。儘管對於鍊表而言,即使排序後,選擇操作也需要 O(n),這是由於缺乏隨機訪問造成的。通常的,排序需要耗費 O(n log n) 的時間,其中 n 是列表的長度,儘管對於非比較算法而言可能更低一些,如基數排序和計數排序。
相比將整個列表或數組進行排序,還可以用偏排序來選擇第 k 小或第 k 大的元素。第 k 小的(第 k 大的) 也就是偏排序後列表中最大的 (最小的) 那個 – 這在數組中會耗費 O(1) 來訪問,在鍊表中會耗費 O(k)。
基於分區的選擇
[編輯]![]() | 此章節尚無任何內容,需要擴充。 (2018年8月28日) |
通過選擇增量排序
[編輯]![]() | 此章節尚無任何內容,需要擴充。 (2018年8月28日) |
參見
[編輯]參考文獻
[編輯]外部連結
[編輯]- "Lecture notes for January 25, 1996: Selection and order statistics (頁面存檔備份,存於互聯網檔案館)", ICS 161: Design and Analysis of Algorithms, David Eppstein