主講人：呂敏Email:{lvmin05@}Spring2012，USTC算法基礎(chǔ)算法基礎(chǔ)2022/12/202第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/172第七講順序統(tǒng)計學(xué)內(nèi)容提要：問題描述在一個由n個元素組成的集合中，第i個順序統(tǒng)計量是該集合中第i個小的元素。一個中位數(shù)是它所在集合的“中點元素”。當(dāng)n為奇數(shù)時，中位數(shù)是唯一的，i=(n+1)/2；當(dāng)n為偶數(shù)時，中位數(shù)有兩個，即：i=n/2(下中位數(shù))和i=n/2+1（上中位數(shù)）不考慮n的奇偶性，中位數(shù)總出現(xiàn)在處（下中位數(shù)）和處（上中位數(shù)）。本書中所用的“中位數(shù)”指的是下中位數(shù)。選擇問題：從一個由n個不同數(shù)值構(gòu)成的集合中，選擇其第i個順序統(tǒng)計量。輸入：一個包含n個（不同的）數(shù)的集合A和一個數(shù)i,1≤

i≤n輸出：元素

，它恰大于A中其它i-1個元素。2022/12/203問題描述在一個由n個元素組成的集合中，第i個順序統(tǒng)計量是該集問題描述選擇問題可以在O(nlgn)時間內(nèi)解決：用堆排序或合并排序?qū)斎霐?shù)據(jù)進(jìn)行排序再在輸出數(shù)組中標(biāo)出第i個元素即可。還有其他更快的算法。問題描述2022/12/205第七講順序統(tǒng)計學(xué)內(nèi)容提要：

最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/175第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值最小/最大值：進(jìn)行n-1次比較，時間復(fù)雜度為θ(n)；假設(shè)集合放在數(shù)組A中，且length[A]=n。2022/12/206MINIMUM(A)min←A[1];fori

←2tolength[A]doifmin>A[i]thenmin←A[i]returnmin總共比較了n

-1次，時間復(fù)雜度：O(n)最小值和最大值最小/最大值：進(jìn)行n-1次比較，時間復(fù)雜度為θ最小值和最大值同時找最小值和最大值1）記錄比較過程中遇到的最小值和最大值；2）成對處理元素，先比較兩個輸入元素，把較小者與當(dāng)前最小值比較，較大者與當(dāng)前最大值比較（每對元素需要3次比較）2022/12/207MAX-MINIMUM(A)iflength[A]isoddthenmin←A[1];max

←

min;elsemin←MIN(A[1],A[2]),max

←MAX(A[1],A[2]);i++;whilei≤length[A]

min

←MIN(

MIN(A[i],A[i+1]),min)

max

←MAX(MAX(A[i],A[i+1]),max)

i

←i+2;endreturnmin,max最小值和最大值同時找最小值和最大值2022/12/177MA最小值和最大值如何設(shè)定當(dāng)前最小值和最大值的初始值：依賴于n的奇偶性如果n是奇數(shù)，將最小值和最大值都設(shè)為第一個元素的值；如果n是偶數(shù)，就對前兩個元素做一次比較，以決定最小值和最大值的初始值。總的比較次數(shù)：如果n是奇數(shù)，那么總共做了次比較如果n是偶數(shù)，總共做了次比較。2022/12/208時間復(fù)雜度為：O(n)最小值和最大值如何設(shè)定當(dāng)前最小值和最大值的初始值：依賴于n的2022/12/209第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值

以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/179第七講順序統(tǒng)計學(xué)內(nèi)容提要：以期望線性時間做選擇基本思想：采用分治策略，借鑒快速排序的隨機(jī)劃分法，對輸入數(shù)組進(jìn)行遞歸劃分，但是只處理劃分的一邊。2022/12/2010RANDOMIZED-SELECT(A,p,r,i)ifp=r//臨界問題處理thenreturnA[p]q

←RANDOMIZED-PARTITION(A,p,r)//進(jìn)行劃分，返回劃分元下標(biāo)k

←q–p+1ifi=kthenreturnA[q];elseifi<kthenreturnRANDOMIZED-SELECT(A,p,q-1,i)elsereturnRANDOMIZED-SELECT(A,q+1,r,i–k)以期望線性時間做選擇基本思想：采用分治策略，借鑒快速排序的隨以期望線性時間做選擇2022/12/2011以期望線性時間做選擇2022/12/1711以期望線性時間做選擇2022/12/2012時間復(fù)雜度分析：以期望線性時間做選擇2022/12/1712時間復(fù)雜度分析：以期望線性時間做選擇2022/12/2013以期望線性時間做選擇2022/12/1713以期望線性時間做選擇2022/12/2014以期望線性時間做選擇2022/12/1714以期望線性時間做選擇2022/12/2015以期望線性時間做選擇2022/12/17152022/12/2016第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/1716第七講順序統(tǒng)計學(xué)內(nèi)容提要：最壞情況線性時間的選擇基本思想：類似RandomizedSelect算法，通過對輸入數(shù)組進(jìn)行遞歸劃分來找出所求元素，但是算法保證每次對數(shù)組的劃分是個好劃分主要步驟：2022/12/2017最壞情況線性時間的選擇基本思想：類似RandomizedSe最壞情況線性時間的選擇2022/12/2018最壞情況線性時間的選擇2022/12/1718最壞情況線性時間的選擇時間復(fù)雜度分析：由上頁圖示，可知至少有的元素較x來得大。同理，至少有3n/10-6的元素較x來得小。如果Partition過，i

≠k，則至多只要在7n/10+6個元素的情況下遞歸調(diào)用Select。而先前找出小組中位數(shù)的中位數(shù)時，只在n/5個元素的情況下遞歸調(diào)用

Select。故T(n)=T()+T(7n/10+6)+Θ(n),forn>=140.2022/12/2019最壞情況線性時間的選擇時間復(fù)雜度分析：2022/12/171最壞情況線性時間的選擇利用替換法，令T(n)=O(cn)2022/12/2020假設(shè)n>140時，c>=20a，上式就可以成立！最壞情況線性時間的選擇利用替換法，令T(n)=O(最壞情況線性時間的選擇2022/12/2021最壞情況線性時間的選擇2022/12/1721謝謝！2022/12/2022Q&A作業(yè)：9.1-19.3-6謝謝！2022/12/1722Q&A主講人：呂敏Email:{lvmin05@}Spring2012，USTC算法基礎(chǔ)算法基礎(chǔ)2022/12/2024第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/172第七講順序統(tǒng)計學(xué)內(nèi)容提要：問題描述在一個由n個元素組成的集合中，第i個順序統(tǒng)計量是該集合中第i個小的元素。一個中位數(shù)是它所在集合的“中點元素”。當(dāng)n為奇數(shù)時，中位數(shù)是唯一的，i=(n+1)/2；當(dāng)n為偶數(shù)時，中位數(shù)有兩個，即：i=n/2(下中位數(shù))和i=n/2+1（上中位數(shù)）不考慮n的奇偶性，中位數(shù)總出現(xiàn)在處（下中位數(shù)）和處（上中位數(shù)）。本書中所用的“中位數(shù)”指的是下中位數(shù)。選擇問題：從一個由n個不同數(shù)值構(gòu)成的集合中，選擇其第i個順序統(tǒng)計量。輸入：一個包含n個（不同的）數(shù)的集合A和一個數(shù)i,1≤

i≤n輸出：元素

，它恰大于A中其它i-1個元素。2022/12/2025問題描述在一個由n個元素組成的集合中，第i個順序統(tǒng)計量是該集問題描述選擇問題可以在O(nlgn)時間內(nèi)解決：用堆排序或合并排序?qū)斎霐?shù)據(jù)進(jìn)行排序再在輸出數(shù)組中標(biāo)出第i個元素即可。還有其他更快的算法。問題描述2022/12/2027第七講順序統(tǒng)計學(xué)內(nèi)容提要：

最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/175第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值最小/最大值：進(jìn)行n-1次比較，時間復(fù)雜度為θ(n)；假設(shè)集合放在數(shù)組A中，且length[A]=n。2022/12/2028MINIMUM(A)min←A[1];fori

←2tolength[A]doifmin>A[i]thenmin←A[i]returnmin總共比較了n

-1次，時間復(fù)雜度：O(n)最小值和最大值最小/最大值：進(jìn)行n-1次比較，時間復(fù)雜度為θ最小值和最大值同時找最小值和最大值1）記錄比較過程中遇到的最小值和最大值；2）成對處理元素，先比較兩個輸入元素，把較小者與當(dāng)前最小值比較，較大者與當(dāng)前最大值比較（每對元素需要3次比較）2022/12/2029MAX-MINIMUM(A)iflength[A]isoddthenmin←A[1];max

←

min;elsemin←MIN(A[1],A[2]),max

←MAX(A[1],A[2]);i++;whilei≤length[A]

min

←MIN(

MIN(A[i],A[i+1]),min)

max

←MAX(MAX(A[i],A[i+1]),max)

i

←i+2;endreturnmin,max最小值和最大值同時找最小值和最大值2022/12/177MA最小值和最大值如何設(shè)定當(dāng)前最小值和最大值的初始值：依賴于n的奇偶性如果n是奇數(shù)，將最小值和最大值都設(shè)為第一個元素的值；如果n是偶數(shù)，就對前兩個元素做一次比較，以決定最小值和最大值的初始值?？偟谋容^次數(shù)：如果n是奇數(shù)，那么總共做了次比較如果n是偶數(shù)，總共做了次比較。2022/12/2030時間復(fù)雜度為：O(n)最小值和最大值如何設(shè)定當(dāng)前最小值和最大值的初始值：依賴于n的2022/12/2031第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值

以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/179第七講順序統(tǒng)計學(xué)內(nèi)容提要：以期望線性時間做選擇基本思想：采用分治策略，借鑒快速排序的隨機(jī)劃分法，對輸入數(shù)組進(jìn)行遞歸劃分，但是只處理劃分的一邊。2022/12/2032RANDOMIZED-SELECT(A,p,r,i)ifp=r//臨界問題處理thenreturnA[p]q

←RANDOMIZED-PARTITION(A,p,r)//進(jìn)行劃分，返回劃分元下標(biāo)k

←q–p+1ifi=kthenreturnA[q];elseifi<kthenreturnRANDOMIZED-SELECT(A,p,q-1,i)elsereturnRANDOMIZED-SELECT(A,q+1,r,i–k)以期望線性時間做選擇基本思想：采用分治策略，借鑒快速排序的隨以期望線性時間做選擇2022/12/2033以期望線性時間做選擇2022/12/1711以期望線性時間做選擇2022/12/2034時間復(fù)雜度分析：以期望線性時間做選擇2022/12/1712時間復(fù)雜度分析：以期望線性時間做選擇2022/12/2035以期望線性時間做選擇2022/12/1713以期望線性時間做選擇2022/12/2036以期望線性時間做選擇2022/12/1714以期望線性時間做選擇2022/12/2037以期望線性時間做選擇2022/12/17152022/12/2038第七講順序統(tǒng)計學(xué)內(nèi)容提要：最小值和最大值以期望線性時間做選擇

最壞情況線性時間的選擇2022/12/1716第七講順序統(tǒng)計學(xué)內(nèi)容提要：最壞情況線性時間的選擇基本思想：類似RandomizedSelect算法，通過對輸入數(shù)組進(jìn)行遞歸劃分來找出所求元素，但是算法保