算法設(shè)計與分析 ch3b 學(xué)習(xí)課件

數(shù)據(jù)與知識工程研究中心(2015)海量數(shù)據(jù)計算研究中心MassiveDataComputingLab@HIT算法設(shè)計與分析第三章排序與分治法哈爾濱工業(yè)大學(xué)王宏志wangzh@/pages/wang/數(shù)據(jù)與知識工程研究中心(2015)3.1排序介紹3.2

分治法3.3

mergesort3.4quicksort3.5排序問題的下界Outlines數(shù)據(jù)與知識工程研究中心(2015)3.1introduction排序的概念

排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列例如，將下列關(guān)鍵字序列

52,49,80,36,14,58,61,23,97,75調(diào)整為

14,23,36,49,52,58,61,75,80,97數(shù)據(jù)與知識工程研究中心(2015)一般情況下，假設(shè)含n個記錄的序列為

{R1,R2,…，Rn

}

其相應(yīng)的關(guān)鍵字序列為

{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將式(1)的記錄序列重新排列為

{Rp1,Rp2,…，Rpn}

的操作稱作排序數(shù)據(jù)與知識工程研究中心(2015)例(張三,89),(李四,55),(王五,79),(大麻,92),(李亞鵬,10)元組第一項表示姓名，元組第二項表示成績根據(jù)成績從小到達可以將這些元組排序為(李亞鵬,10),(李四,55),(王五,79),(張三,89),(大麻,92)typedefinestructRecord{charname[20];integerscore;}Record;RecordR[5];R[1]=(張三,89),R[1]=(李四,55),…,R[4]=(李亞鵬,10)數(shù)據(jù)與知識工程研究中心(2015)內(nèi)部排序與外部排序

若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序我們本章主要內(nèi)部排序的各種方法數(shù)據(jù)與知識工程研究中心(2015)內(nèi)部排序方法的分類

在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程有序序列區(qū)

無

序

序

列

區(qū)

使有序區(qū)中記錄的數(shù)目增加一個或幾個的操作稱為一趟排序數(shù)據(jù)與知識工程研究中心(2015)逐步擴大記錄有序序列長度的方法有下列幾類：插入類將無序子序列中的一個或幾個記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度交換類通過“交換”無序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長度歸并類通過“歸并”兩個或兩個以上的記錄有序子序列，逐步增加記錄有序序列的長度其它方法數(shù)據(jù)與知識工程研究中心(2015)3.2Divide-and-Conquer技術(shù)Divide-and-Conquer算法的設(shè)計Divide-and-Conquer算法的分析

設(shè)計過程分為三個階段Divide：整個問題劃分為多個子問題Conquer：求解各子問題(遞歸調(diào)用正設(shè)計的算法)Combine：合并子問題的解,形成原始問題的解數(shù)據(jù)與知識工程研究中心(2015)Divide-and-Conquer算法的設(shè)計數(shù)據(jù)與知識工程研究中心(2015)原始問題求解子問題子問題子問題子問題…求解子問題求解子問題子問題解子問題解子問題解…合并子解問題分解DivideConquerMerge原始問題的解分析過程建立遞歸方程求解遞歸方程的建立方法設(shè)輸入大小為n,T(n)為時間復(fù)雜性當n<c,

T(n)=

(1)數(shù)據(jù)與知識工程研究中心(2015)Divide-and-Conquer算法的分析數(shù)據(jù)與知識工程研究中心(2015)Divide階段的時間復(fù)雜性劃分問題為a個子問題。每個子問題大小為n/b。劃分時間可直接得到=D(n)Conquer階段的時間復(fù)雜性遞歸調(diào)用Conquer時間=aT(n/b)Combine階段的時間復(fù)雜性時間可以直接得到=C(n)總之T(n)=(1)ifn<c

T(n)=aT(n/b)+D(n)+C(n)otherwise求解遞歸方程T(n)使用第二章的方法數(shù)據(jù)與知識工程研究中心(2015)數(shù)據(jù)與知識工程研究中心(2015)整數(shù)乘法

問題定義輸入：n位二進制整數(shù)X和Y輸出：X和Y的乘積通常，計算X*Y時間復(fù)雜性位O(n2)，我們給出一個復(fù)雜性為O(n1.59)的算法。

ABn/2位X=n/2位

CDn/2位Y=n/2位XY=(A2n/2+B)(C2n/2+D)=AC2n+((A-B)(C-D)+BC+AD)2n/2

+BD算法計算A-B和C-D；計算n/2位乘法AC、BD、(A-B)(C-D)；計算(A-B)(C-D)+BC+AD；AC左移n位，((A-B)(C-D)+BC+AD)左移n/2位；計算XY。算法的數(shù)學(xué)基礎(chǔ)建立遞歸方程

T(n)=

(1)ifn=1T(n)=3T(n/2)+O(n) ifn>1使用Master定理

T(n)=O(nlog3)=O(n1.59)算法的分析數(shù)據(jù)與知識工程研究中心(2015)例2

max與min數(shù)據(jù)與知識工程研究中心(2015)問題定義輸入：數(shù)組A[1,…,n]輸出：A中的max和min通常，直接掃描需要2n-2次比較操作我們給出一個僅需

3n/2-2

次比較操作的算法。數(shù)據(jù)與知識工程研究中心(2015)基本思想基于任務(wù)不同將問題劃分成兩個子問題一個子問題求解max另一個子問題求解min將A[i]與A[n-i+1]比較，i=1,2,…,n/2較小的元素放在前面，較大的元素放在后面最小元素出現(xiàn)在A[1,2,…

n/2]中最大元素A[

n/2,…,n]中數(shù)據(jù)與知識工程研究中心(2015)算法Max-min(A)Input:數(shù)組A[1,…,n]Output:數(shù)組A[1,…,n]中的max和min1.Fori1Ton/2Do2.IFA[i]>A[n-i+1]THENswap(A[i],A[n-i+1]);3.maxA[n];minA[1];4.For2Ton/2Do5.IFA[i]<minTHENminA[i];6.IFA[n-i+1]>maxTHENmaxA[n-i+1];7.printmax,min;算法復(fù)雜性

3n/2-2

次比較操作數(shù)據(jù)與知識工程研究中心(2015)基于分治思想的排序算法94865213710劃分x1,x2,…,xkxk+1,…,xn遞歸求解遞歸求解a1,a2,…,akbk+1,…,bn合并y1,…,yn劃分的策略1.選擇一個位置將數(shù)組劃分成兩個部分mergesort9,4,8,6,52,1,3,7,104,5,6,8,91,2,3,7,101,2,3,4,5,6,7,8,9,104,6,5,2,1,39,8,7,101,2,3,4,5,67,8,9,10合并策略不同的劃分策略對應(yīng)不同的合并策略由于分治思想涉及到遞歸調(diào)用，需要關(guān)心子問題的最一般形式在排序問題中，子問題一般形式就是將A[i,…,j]中的元素排序2.選擇一個劃分標準x,根據(jù)元素與x的大小關(guān)系來劃分

quicksort數(shù)據(jù)與知識工程研究中心(2015)3.3

Merge-sort算法

＝A[i,…,j]Divide：本質(zhì)上僅需產(chǎn)生劃分位置k第一個子問題是A[i,…,k]第二個子問題是A[k+1,…,j]為使得兩個問題的大小大致相當，k可以如下產(chǎn)生

k=(i+j)/2數(shù)據(jù)與知識工程研究中心(2015)＝A[i,…,j]Conquer:遞歸求解就是算法的遞歸調(diào)用Mergesort(A,i,k)；//求解第一個子問題Mergesort(A,k+1,j)；//求解第二個子問題數(shù)據(jù)與知識工程研究中心(2015)combine:將兩個有序序列合并成一個有序序列1.li;hk+1;t=i

//設(shè)置指針2.Whilel

k&h<jDoIFA[l]<A[h]THENB[t]

A[l];l

l+1;tt+1;ELSEB[t]

A[h];h

h+1;tt+1;3.IFl<kTHEH//第一個子問題有剩余元素

Forv

lTokDo

B[t]

A[v];tt+1;4.IFh<jTHEN//第二個子問題有剩余元素

Forv

hTojDo

B[t]

A[v];tt+1;4,5,6,8,91，2，3，7,10combine4,5,6,8,91，2，3，7,10combine4,5,6,8,91，2，3，7,10combine1,4,5,6,8,91，2，3，7,10combine1,24,5,6,8,91，2，3，7,10combine1,2,34,5,6,8,91，2，3，7,10combine1,2,3,4,4,5,6,8,91，2，3，7,10combine1,2,3,4,54,5,6,8,91，2，3，7,10combine1,2,3,4,5,64,5,6,8,91，2，3，7,10combine1,2,3,4,5,6,7,4,5,6,8,91，2，3，7,10combine1,2,3,4,5,6,7,8,4,5,6,8,91，2，3，7,10combine1,2,3,4,5,6,7,8,94,5,6,8,91，2，3，7,10combine1,2,3,4,5,6,7,8,9,10數(shù)據(jù)與知識工程研究中心(2015)MergeSort(A,i,j)Input:A[i,…,j]Output:排序后的A[i,…,j]k(i+j)/2;MergeSort(A,i,k);MergeSort(A,k+1,j);4.li;hk+1;t=i

//設(shè)置指針5.Whilel

k&h<jDo6.IFA[l]<A[h]THENB[t]

A[l];l

l+1;tt+1;7.ELSEB[t]

A[h];h

h+1;tt+1;8.IFl<kTHEH//第一個子問題有剩余元素9.Forv

lTokDo10.B[t]

A[v];tt+1;11.IFh<jTHEN//第二個子問題有剩余元素12.Forv

hTojDoB[t]

A[v];tt+1;Forv

iTojDo//將歸并后的數(shù)據(jù)復(fù)制到A中

A[v]

B[v]；Mergesort算法T(n)=2T(n/2)+O(n)T(n)=O(nlogn)435819267435819267中位數(shù)問題定義Input:

由n個數(shù)構(gòu)成的多重集合XOutput:

x

X使得-1|{y

X|y<x}|-|{y

X|y>x}|1[Blumetal.STOC’72&JCSS’73]A“shining”paperbyfiveauthors:ManuelBlum(TuringAward1995)RobertW.Floyd(TuringAward1978)VaughanR.PrattRonaldL.Rivest(TuringAward2002)RobertE.Tarjan(TuringAward1986)從n個數(shù)中選取中位數(shù)需要的比較操作的次數(shù)介于

1.5n到

5.43n之間中位數(shù)選取問題的復(fù)雜度上界3n+o(n)bySchonhage,Paterson,andPippenger(JCSS1975).2.95nbyDorandZwick

(SODA1995,SIAMJournalonComputing1999).下界2n+o(n)byBentandJohn(STOC1985)(2+2-80)nbyDorandZwick(FOCS1996,SIAMJournalonDiscreteMath2001).比較操作次數(shù)的上下界線性時間選擇本節(jié)討論如何在O(n)時間內(nèi)從n個不同的數(shù)中選取第i大的元素中位數(shù)問題也就解決了，因為選取中位數(shù)即選擇第n/2-大的元素Input:

n個(不同)數(shù)構(gòu)成的集合X,整數(shù)i,其中1

i

nOutput:

x

X使得X中恰有i-1個元素小于x第一步:分組，每組5個數(shù)

最后一組可能少于5個數(shù)求解步驟第二步:將每組數(shù)分別用InsertionSort排序

選出每組元素的中位數(shù)排序每組數(shù)時，比較操作的次數(shù)為5(5-1)/2=10次總共需要10*

n/5次比較操作第三步:

遞歸調(diào)用算法求得這些中位數(shù)的中位數(shù)(MoM)

時間復(fù)雜性：T(

n/5

)第四步:用

MoM完成劃分>MoM<MoMMoMxX>X<時間復(fù)雜性O(shè)(n)第五步:遞歸設(shè)x是中位數(shù)的中位數(shù)(MoM),劃分完成后其下標為k

如果i=k,則返回x

如果i<k,則在第一個部分遞歸選取第i-大的數(shù)如果i>k,則在第三個部分遞歸選取第(i-k)-大的數(shù)<MoM>MoMMoMxX>X<算法Select(A,i)Input:數(shù)組A[1:n],1

i

nOutput:A[1:n]中的第i-大的數(shù)

1.forj1ton/52.InsertSort(A[(j-1)*5+1:(j-1)*5+5]);3.swap(A[j],A[[(j-1)*5+3]);4.xSelect(A[1:n/5],n/10);5.kpartition(A[1:n],x);6.ifk=ithenreturnx;7.elseifk>ithenretrunSelect(A[1:k-1],i);8.elseretrunSelect(A[k+1:n],i-k);

第五步第二步第一步第三步第四步算法Select(A,i)Input:數(shù)組A[1:n],1

i

nOutput:A[1:n]中的第i-大的數(shù)

1.forj1ton/52.InsertSort(A[(j-1)*5+1:(j-1)*5+5]);3.swap(A[j],A[[(j-1)*5+3]);4.xSelect(A[1:n/5],n/10);5.kpartition(A[1:n],x);6.ifk=ithenreturnx;7.elseifk>ithenretrunSelect(A[1:k-1],i);8.elseretrunSelect(A[k+1:n],i-k);

???O(n)T(

n/5)O(n)算法分析觀察第五步的處理過程第五步至少刪除了

3n/10

個數(shù)n-

3n/107n/10+6

如果時間復(fù)雜度是輸入規(guī)模的遞增函數(shù)

則第五步的時間開銷不超過T(7n/10+6)

(1)ifn

CT

n/5+T(7n/10+6)+

(n)

ifn>CT(n)

T(n)=O(n)數(shù)據(jù)與知識工程研究中心(2015)

3.4

QuickSort數(shù)據(jù)與知識工程研究中心(2015)Partitionsort94865213710=A[i,…,j]劃分x1,x2,…,xkxk+1,…,xn遞歸求解遞歸求解a1,a2,…,akbk+1,…,bn合并1,2,3,4,5,6,7,8,9,104,6,5,2,1,39,8,7,101,2,3,4,5,67,8,9,10基本思想Divide：確定一個劃分標準x，將數(shù)組中小于x的元素放到數(shù)組的前面部分，大于x的元素放到數(shù)組的后面部分，并返回一個劃分k；Conquer：遞歸調(diào)用算法將A[i,…,k]和A[k+1,…,j]求解。Combine：無操作數(shù)據(jù)與知識工程研究中心(2015)PartitionSort算法框架PartitionSort(A,i,j)Input:A[i,…,j],xOutput:排序后的A[i,…,j]選擇劃分元素x;k=partition(A,i,j,x);

//用x完成劃分partitionSort(A,i,k);//遞歸求解子問題partitionSort(A,k+1,j);//無需額外的合并操作

數(shù)據(jù)與知識工程研究中心(2015)Divide94865213710=A[i,…,j]94865213710=A[i,…,j]x=73486521

9710=A[i,…,j]3416528

9710=A[i,…,j]341652

8

9710=A[i,…,j]341652=A[i,…,high]89710=A[high+1,…,j]指針low從低區(qū)中找出應(yīng)放到x之后的第一個元素指針high從高區(qū)中找出應(yīng)放到x之前的第一個元素如果確實應(yīng)該交low和high標記的兩個元素的位置，則交換否則劃分位置就是high數(shù)據(jù)與知識工程研究中心(2015)Divide過程的算法描述Partition(A,i,j,x)Input:A[i,…,j],xOutput:劃分位置k使得A[i,…,k]中的元素均小于x且A[k+1,…,j]

中的元素均大于等于xlow

i;high

j;While(low<high)Doswap(A[low],A[high]);While(A[low]<x)Do

low

low+1;While(A[high]>=x)Do

high

high-1;return(high)數(shù)據(jù)與知識工程研究中心(2015)PartitionSort算法Partition(A,i,j,x)low

i;high

j;While(low<high)Doswap(A[low],A[high]);While(A[low]<x)Do

low

low+1;While(A[high]>=x)Do

high

high-1;return(high)PartitionSort(A,i,j)Input:A[i,…,j],xOutput:排序后的A[i,…,j]x

A[i];//以確定的策略選擇xk=partition(A,i,j,x);

//用x完成劃分partitionSort(A,i,k);//遞歸求解子問題partitionSort(A,k+1,j);

數(shù)據(jù)與知識工程研究中心(2015)最好情況

:

(nlogn)數(shù)組被分為大致相等的兩個部分.

需要logn

輪.

每輪需要O(n)次比較算法復(fù)雜性的分析數(shù)據(jù)與知識工程研究中心(2015)最壞情況

:

(n2)每一輪用最大或者最小元素劃分算法復(fù)雜性的分析數(shù)據(jù)與知識工程研究中心(2015)平均情況:

(nlogn)算法復(fù)雜性的分析數(shù)據(jù)與知識工程研究中心(2015)算法復(fù)雜性的分析數(shù)據(jù)與知識工程研究中心(2015)算法復(fù)雜性的分析數(shù)據(jù)與知識工程研究中心(2015)隨機QuickSort算法Partition(A,i,j,x)low

i;high

j;While(low<high)Doswap(A[low],A[high]);While(A[low]<x)Do

low

low+1;While(A[high]>=x)Do

high

high-1;return(high)QuickSort(A,i,j)Input:A[i,…,j],xOutput:排序后的A[i,…,j]temprand(i,j);//產(chǎn)生i，j之間的隨機數(shù)x

A[temp];//以確定的策略選擇xk=partition(A,i,j,x);

//用x完成劃分partitionSort(A,i,k);//遞歸求解子問題partitionSort(A,k+1,j);

數(shù)據(jù)與知識工程研究中心(2015)算法性能的分析

基本概念

S(i)表示S中階為i的元素

例如,S(1)和S(n)分別是最小和最大元素隨機變量Xij定義如下:

Xij=1如果S(i)和S(j)在運行中被比較,否則為0Xij是S(i)和S(j)的比較次數(shù)算法的比較次數(shù)為算法的平均復(fù)雜性為數(shù)據(jù)與知識工程研究中心(2015)

計算E[Xij]

設(shè)pij為S(i)和S(j)在運行中比較的概率,則

E[Xij]=pij1+(1-pij)0=pij關(guān)鍵問題成為求解pij數(shù)據(jù)與知識工程研究中心(2015)

求解Pij我們可以用樹表示算法的計算過程

yT1T2yxT11T12xT21T22

我們可以觀察到如下事實:

一個子樹的根必須與其子樹的所有節(jié)點比較不同子樹中的節(jié)點不可能比較任意兩個節(jié)點至多比較一次數(shù)據(jù)與知識工程研究中心(2015)

當S(i),S(i+1),…,S(j)在同一子樹時,

S(i)和S(j)才可能比較只有S(i)或S(j)先于S(i+1),…,S(j-1)被選為劃分點時,S(i)和S(j)才可能比較

S(i),S(i+1),…,S(j)等可能地被選為劃分點,所以S(i)和S(j)

進行比較的概率是:2/(j-i+1),即pij=2/(j-i+1)數(shù)據(jù)與知識工程研究中心(2015)

現(xiàn)在我們有

定理.隨機排序算法的期望時間復(fù)雜性為O(nlogn)3.5排序問題的下界問題的下界是解決該問題的算法所需要的最小時間復(fù)雜性。 ☆

最壞情況下界

☆

平均情況下界問題的下界是不唯一的例如.

(1),

(n),

(nlogn)都是排序的下界數(shù)據(jù)與知識工程研究中心(2015)如果一個問題的最高下界是

(nlogn)而當前最好算法的時間復(fù)雜性是O(n2).我們可以尋找一個更高的下界.我們可以設(shè)計更好的算法.下界和算法都是可以改進的.如果一個問題的下界是

(nlogn)且算法的時間復(fù)雜性是

O(nlogn),那么這個算法是最優(yōu)的。數(shù)據(jù)與知識工程研究中心(2015)

3個元素有6種排列 a1 a2 a3 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1數(shù)據(jù)與知識工程研究中心(2015)最壞情況下排序的下界直接插入排序輸入:(2,3,1) (1)a1:a2

(2)a2:a3,a2

a3

(3)a1:a2,a1

a2

輸入:(2,1,3) (1)a1:a2,a1

a2

(2)a2:a3數(shù)據(jù)與知識工程研究中心(2015)直接插入排序的決策樹數(shù)據(jù)與知識工程研究中心(2015)冒泡排序的決策樹數(shù)據(jù)與知識工程研究中心(2015)排序的下界為了找到排序的下界，我們需要找到二叉樹的最小高度.有n!種不同排列

二叉決策樹有n!個葉子結(jié)點.平衡樹高度最小

log(n!)

=

(nlogn)

排序的下界是:

(nlogn)數(shù)據(jù)與知識工程研究中心(2015)方法

1:數(shù)據(jù)與知識工程研究中心(2015)方法2:Stirling近似:n!

logn!

log

nlogn

(nlogn)

數(shù)據(jù)與知識工程研究中心(2015)排序的平均情況下界仍利用決策樹排序算法的平均復(fù)雜性用從根結(jié)點到每個葉子結(jié)點的路徑長度的總長度描述。n!當樹平衡時這個值最小. (所有葉子結(jié)點的深度是

d或

d

1)數(shù)據(jù)與知識工程研究中心(2015)數(shù)據(jù)與知識工程研究中心(2015)平均情況下排序的下界計算最小路徑長度和數(shù)據(jù)與知識工程研究中心(2015)1.

有c