1、1,.,Order Statistics,（次序統(tǒng)計）,- 找第k最小元,2,問題： 已知n元數(shù)組A1:n，確定其中第k最小的元。, 最容易想到的算法是采用一種分類算法先將數(shù)組按不降的次序排好，然后從排好序的數(shù)組中撿出第k小的元素。但這樣的算法在最壞情況下至少是O(nlogn)，甚至可達(dá)O(n)。 實際上，我們可以設(shè)計出時間復(fù)雜性為O(n)的算法。,3,6.1,找第k最小元,- 分治策略劃分,4,按某個mS，把S分成三個小集合s1，s2，s3 例如，取m=6 3 2 5 6 6 6 9 7 8 8 s1 s2 s3,如果 k|s1|,那么k元就在s1中。 如果 k|s1|+|s2|,那么k元就

2、在s2中,即k元就是m=6。 如果 k|s1|+|s2|,那么k元就在s3中。 這就把問題分成了小的問題，s1 或s3。,5,但是要得到O(n)算法，還必須： s1，s2都不超過S長的某固定分?jǐn)?shù)，以便 遞歸。顯然，m 最好是中間元或接近中 間元。 2.找m的時間不得高于O(n)。,6,下面舉例說明找m的方法： 例如，n=35, m=?,7,把S分成幾個小序列，每個序列5個元，分別分揀好。把所有中間元合成序列M，求M序列中間元m。 我們按上圖：5個元小序列按縱向分揀（上小，下大），M是按橫向分揀（左小，右大），那么由圖可知： 至少有 的元大于或等于m，即小于m的元（集合s1）最 多有 個元。 至

3、少有 的元小于或等于m，即大于m的元（集合s3）最 多有 個元。,8,算法3.6.1： 查找S中第k最小元 Procedure FIND( k, S ) （P.59） 1. if |S|50 then begin sort S； return Kth smallest element in S end else begin 2. 把S分成5元小序列，不足5的余數(shù)另行處理； 分揀5元小序列； 設(shè)M為5元小序列中間元的集合； 3. mFIND( , M ),9,4. 把S如上述分成s1，s2，s3； （m為分裂元，3個集合中的元分別小于、等于、大于m） 5. if |s1| k then retu

4、rn FIND( k, s1 ) else 6. if ( |s1| + | s2| k ) then return m else (即 k 元在 s2 中，也就是分裂元 m) return FIND( k - |s1| - |s2|， s3 ) end 注：該算法語句編號與書上有區(qū)別！,2和3是找中間元，3遞歸多次，直到|M|50為止。,10,例如，n=260 第1輪： 2. 把S分成52個5元序列， 3. FIND(26,M)；此時|M|=52(52個中間元的集合) 第2輪： 2. 把M分成10個5元序列， 余下的2個元暫置一邊。 3. FIND（5,M1）； 此時|M1|=10 第3輪： 1. 給出了M1序列第5元 回到第2輪3 回到第1輪3 （mM1的第5元）,11,為什么選5元小序列？ 排列5元小序列的代價不高 算法3.6.1有2次遞歸：3、5或3、6 |M|+|s1|和|M|+|s3|都應(yīng)小于|S|， |M|最多是|S|的 ；|s1|或|s3|最多是|S|的 ； 兩者相加，最多只是,12,6.2,算法的時間復(fù)雜性,13,時間復(fù)雜性: 當(dāng)n50時，執(zhí)行1， T(n)cn for n50 |M|最多只有 ； 第3句最多是 |s1|，|s3|最多是 ； 第5（或6）句最多是