跳至內容

選擇算法

維基百科,自由的百科全書

計算機科學中,選擇算法是一種在列表數組中找到第k個最小數字的算法;這樣的數字被稱為第k個順序統計量。該算法尋找的對象主要有三種:最小最大中位數。已知存在O(n)(最壞情況下為線性時間)的選擇算法,還有對於結構化數據可能有次線性的表現的算法;在極端的情況下,對於已排序數據是O(1)。選擇是一些更複雜問題的子問題,如最近鄰最短路徑問題。 許多選擇算法是由排序算法推廣而來,反之,一些排序算法可由反覆應用選擇算法推導出來。

最簡單的選擇算法是通過遍歷列表找到最小(或最大)的元素,在此過程中跟蹤當前的最小(或最大)值。這種算法與選擇排序有關。相反地,最困難的選擇算法是尋找中位數,這必然需要n/2的空間。 事實上,一個專門的中位選擇算法可用來構造一個一般選擇算法,例如中位數的中位數英語Median of medians。已知最好的選擇算法是快速選擇(quickselect),它與快速排序有關。和快速排序類似,它有漸進最佳的複雜度,但是最壞情況的複雜度較差。不過這可以通過調整基準(pivot)的選擇來優化。

通過排序選擇

通過對列表或數組的排序,然後選擇所需的元素,選擇算法可以規約排序算法。這種方法對於選擇單個元素是低效的,但需要從數組中做出很多選擇時是高效的。在這種情況下,僅僅需要一個起初一個代價昂貴的排序,緊接著就是各種便宜的選擇操作了 – 對於數組而言是 O(1)。儘管對於鍊表而言,即使排序後,選擇操作也需要 O(n),這是由於缺乏隨機訪問造成的。通常的,排序需要耗費 O(n log n) 的時間,其中 n 是列表的長度,儘管對於非比較算法而言可能更低一些,如基數排序計數排序

相比將整個列表或數組進行排序,還可以用偏排序來選擇第 k 小或第 k 大的元素。第 k 小的(第 k 大的) 也就是偏排序後列表中最大的 (最小的) 那個 – 這在數組中會耗費 O(1) 來訪問,在鍊表中會耗費 O(k)。

基於分區的選擇

通過選擇增量排序

參見

參考文獻

外部連結