演算法導論閱讀筆記6-中位數和順序統計量

互異正奇數是什麼意思

在一個由n個元素組成的集合中，第i個順序統計量是該集合中第i小的元素。例如，在一個元素集合中，最小值是第1個順序統計量（i=1），最大值是第n個順序統計量。

假設集合中的元素都是互異的，但可以推廣到集合中包含重複元素的情形。

輸入

：一個包含n個（互異的）數的集合A和一個整數i，1≤i≤n。

輸出

：陣列中的元素x，且A中恰好有i-1個元素小於它。可以在O（nlgn）時間內解決這個選擇問題，因為可以用堆排序或歸併排序對輸入資料進行排序，然後在輸出陣列中根據下標找到第i個元素即可。

最大值和最小值

MINIMUM（A） min = A［1］ for i = 2 to A。length if min > A［i］ min = A［i］ return min

為了確定最小值，必須要做n-1次比較。因此，從所執行的比較次數來看，演算法MINIMUM是最優的。

同時找到最小值和最大值

可以分別獨立地找出最大值和最小值，這各需要n-1次比較，共需2n-2次比較。事實上，只需要最多次比較就可以同時找到最小值和最大值。具體的方法是記錄已知的最小值和最大值。但我們並不是將每一個元素與當前的最大值和最小值進行比較-這樣做的代價是每個元素需要2次比較，而是對輸入元素成對地進行處理。首先，我們將一對輸入元素相互進行比較，然後把較小的與當前最小值比較，把較大的與當前最大值進行比較。這樣，對每對元素共需3次比較。如果n為奇數，我們將最大值和最小值的初值都設為第一個元素的值，然後成對地處理剩下的元素。如果n是偶數，就對前兩個元素進行一次比較，以決定最大值和最小值的初值，然後成對地處理餘下的元素。

期望時間為線性時間的選擇演算法

一般選擇問題看起來要比找最小值這樣的簡單問題更難。但令人驚奇的是，這兩個問題的漸近執行時間卻是相同的：Θ（n）。以快速排序演算法為模型，將輸入陣列進行遞迴劃分。但與快速排序不同的是，快速排序會遞迴處理劃分的兩邊，而RANDOMIZED-SELECT只處理劃分的一邊。RANDOMIZED-SELECT的期望執行時間為Θ（n）。這裡，假設輸入資料都是互異的。

RANDOMIZED-SELECT（A， p， r， i） if p == r return A［p］ q = RANDOMIZED-PARTITION（A， p， r） k = q - p + 1 if i == k return A［q］ else if i < k return RANDOMIZED-SELECT（A， p， q-1， i） else return RANDOMIZED-SELECT（A， q+1， r， i-k）

最壞情形執行時間為Θ（n 2）。期望執行時間為O（n），假設元素是互異的。

最壞情形為線性時間的選擇演算法 將輸入陣列的n個元素劃分為

組，每組5個元素，且至多隻有一組由剩下的n mod 5個元素組成。尋找這

組中每一組的中位數：首先對每組元素進行插入排序，然後確定每組有序元素的中位數。對第2步中找出的

箇中位數，遞迴呼叫SELECT已找出其中位數x。利用修改過的PARTITION版本，按中位數的中位數x對輸入陣列進行劃分。讓k比劃分的低區中的元素數目多1，因此x是第k小的元素，並且有n-k個元素在劃分的高區。如果i=k，則返回x。如果i

k，則在高區遞迴查詢第i-k小的元素。