算法設(shè)計(jì)與分析分治法

關(guān)于算法設(shè)計(jì)與分析分治法第1頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五2subproblem2ofsizen/2subproblem1ofsizen/2asolutiontosubproblem2aproblemofsizenasolutiontosubproblem1asolutiontotheoriginalproblem分治法的基本思想第2頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五3分治法的基本思想

將規(guī)模為N的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題,使這些子問(wèn)題相互獨(dú)立可分別求解,再將k個(gè)子問(wèn)題的解合并成原問(wèn)題的解.如子問(wèn)題的規(guī)模仍很大,則反復(fù)分解直到問(wèn)題小到可直接求解為止。在分治法中,子問(wèn)題的解法通常與原問(wèn)題相同,自然導(dǎo)致遞歸過(guò)程。第3頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五4一個(gè)簡(jiǎn)單的例子：N個(gè)數(shù)字求和，如何用分治法解決？是不是分治法一定比蠻力法高效呢？串行計(jì)算并行計(jì)算通過(guò)分治法解決大問(wèn)題的時(shí)間等于所有解決小問(wèn)題的時(shí)間？T(n)=aT(n/b)+f(n)劃分為規(guī)模為n/b的小問(wèn)題a個(gè)小問(wèn)題解決大問(wèn)題的消耗的時(shí)間合并小問(wèn)題消耗的時(shí)間第4頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五5T(n)=aT(n/b)+f(n)遞推式的解法直接使用公式寫(xiě)出分治法解決n個(gè)數(shù)字相加問(wèn)題的效率類(lèi)型，設(shè)每次分為2個(gè)子問(wèn)題第5頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五6本章解決的問(wèn)題：排序查找大整數(shù)乘法矩陣乘法最近對(duì)凸包二叉樹(shù)遍歷第6頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五74.1合并排序

問(wèn)題：

將n個(gè)元素排成非遞減順序。思考如何使用分治法將大問(wèn)題分成小問(wèn)題？第7頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五8思想83297154123456788329238914577154832938291745832971547154分合第8頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五9算法思路：

若n為1,算法終止;否則,將n個(gè)待排元素分割成k(k=2)個(gè)大致相等子集合A、B,對(duì)每一個(gè)子集合分別遞歸排序,再將排好序的子集歸并為一個(gè)集合。第9頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五10合并排序的遞歸算法算法MergeSort(A[0..n-1])//輸入：未排序序列A[0..n-1]//輸出：已排序序列A[0..n-1]ifn>1copyA[0..n/2-1]toB[0..n/2-1]copyA[n/2..n-1]toC[0..n/2-1]MergeSort(B)MergeSort(C)

Merge(B,C,A)

當(dāng)前n規(guī)模的問(wèn)題，分成2個(gè)子問(wèn)題以同樣的方式解決子問(wèn)題用歸并排序，形成最終的有序數(shù)組第10頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五11Merge(B,C,A)是將有序數(shù)組B、C合并為有序數(shù)組A的算法。稱(chēng)為歸并排序歸并排序示例：13491334672561234569133467B數(shù)組C數(shù)組第11頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五12前提：數(shù)組B及數(shù)組C已經(jīng)有序。

比較數(shù)組B的第一個(gè)記錄與數(shù)組C的第一個(gè)記錄將KEY值小者輸出至數(shù)組A，再?gòu)南鄳?yīng)數(shù)組讀進(jìn)一個(gè)記錄，替代已被輸出的記錄，再繼續(xù)比較。結(jié)束：直至有一個(gè)數(shù)組的記錄已被窮盡，然后再將未窮盡的數(shù)組上的所有記錄拷貝到輸出數(shù)組A上。第12頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五13Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])i=0,j=0,k=0;whilei<pandj<qdoifB[i]≤C[j]A[k]=B[i],i=i+1elseA[k]=C[j],j=j+1k=k+1ifi=pcopyC[j..q-1]toA[k..p+q-1]elsecopyB[i..p-1]toA[0..p+q-1]定義各數(shù)組的指針B，C數(shù)組都沒(méi)處理完比較，輸出小的值到A；且輸出值的數(shù)組指針后移若因?yàn)锽數(shù)組結(jié)束，跳出循環(huán)將C數(shù)組剩下的全部放入A數(shù)組第13頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五14合并排序的效率分析ifn>1copyA[0..n/2-1]toB[0..n/2-1]copyA[n/2..n-1]toC[0..n/2-1]MergeSort(B)MergeSort(C)

Merge(B,C,A)

基本操作？？似乎較難判斷。寫(xiě)出總體工作量表達(dá)式。設(shè)n=2k,總工作量表示為：C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)C(1)=0第14頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五15

簡(jiǎn)寫(xiě)為C(n)=2C(n/2)+Cmerge(n)+kn基本操作比較？拷貝？(比較的次數(shù)不會(huì)大于拷貝的次數(shù))是否和其他因素相關(guān)？最壞情況如何？歸并排序的效率Cmerge(n)=n,C

(n)=2C(n/2)+sn解得C(n)=nlog2n-n+1∈Θ(nlog2n)C(n)=(1次除法)+2Ccopy(n/2)+2C(n/2)+Cmerge(n)第15頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五16合并排序結(jié)論最壞情況Θ(nlog2n)優(yōu)點(diǎn)：合并排序在最壞情況下的鍵值比較次數(shù)十分接近于任何基于比較的排序算法在理論上能夠達(dá)到的最少次數(shù)合并排序精確解Cworst(n)=nlog2n-n+1理論最小值nlog2n-1.44n向上取整缺點(diǎn)：需要線性的額外空間，體現(xiàn)在何處？雖然合并也可做到“在位”，但導(dǎo)致算法過(guò)于復(fù)雜。第16頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五174.2快速排序算法思路:對(duì)于輸入A[0..n-1]，按以下三個(gè)步驟進(jìn)行排序：(1)分區(qū):取A中的一個(gè)元素為支點(diǎn)(pivot)將A[0..n-1]劃分成3段:A[0..s-1],A[s],A[s+1..n-1],使得

A[0..s-1]中任一元素A[s],A[s+1..n-1]中任一元素A[s];下標(biāo)s在劃分過(guò)程中確定。(2)遞歸求解:遞歸調(diào)用快速排序法分別對(duì)A[0..s-1]和A[s+1..n-1]排序。(3)合并:合并A[0..s-1],A[s],A[s+1..n-1]為A[0..n-1]第17頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五18493865971327一趟排序后{273813}49{769765}分別快排{13}27{38}{65}76{97}第18頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五19快速排序算法QuickSort(A[l..r])//使用快速排序法對(duì)序列或者子序列排序//輸入：子序列A[l..r]或者序列本身A[0..n-1]//輸出：非遞減序列Aifl<r

s←Partition(A[l..r]) QuickSort(A[l..s-1]) QuickSort(A[s+1..r])

//s是中軸元素/基準(zhǔn)點(diǎn)，是數(shù)組分區(qū)位置的標(biāo)志中軸元素如何選？選好中軸后如何掃描數(shù)組形成分區(qū)？找到分裂點(diǎn)s，分區(qū)按同樣的方法處理子區(qū)間第19頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五20分區(qū)的例子（雙向掃描）初始數(shù)組A[0..n-1]=[5,3,1,9,8,2,4,7],

取元素A[0]=5作為分裂點(diǎn),紅色表示i上的元素，藍(lán)色表示j上的元素

位置i01234567

5

3198247i，j上的元素和分裂點(diǎn)比較并移動(dòng)對(duì)于i遇到比分裂點(diǎn)大或等于時(shí)停止對(duì)于j遇到比分裂點(diǎn)小或等于時(shí)停止53198247停止后，i<j交換A[i]和A[j]i>j交換分裂點(diǎn)和A[j]i=jA[i]=A[j]=分裂點(diǎn)上的值53148297交換后，i加1，j減153148

297繼續(xù)前面的比較和移動(dòng)

53142

897

53142

897i>j交換分裂點(diǎn)和A[j]

2314

5

897

一次分區(qū)完成

第20頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五21數(shù)組的分區(qū)算法：算法Partition(A[l..r])//輸入：子數(shù)組A[l..r]

//輸出：分裂點(diǎn)/基準(zhǔn)點(diǎn)pivot的位置p←A[l]

i←l;j←r+1

repeat

repeat

i←i+1

untilA[i]≥prepeatj←j–1untilA[j]≤pswap(A[i],A[j])untili≥j

swap(A[i],A[j])

swap(A[l],A[j])returnj第21頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五22快速排序效率分析ifl<r

s←Partition(A[l..r]) QuickSort(A[l..s-1]) QuickSort(A[s+1..r])

基本操作？？似乎較難判斷。寫(xiě)出總體工作量表達(dá)式。C(n)=Cpartition(n)+CQuickSort(s前面)+CQuickSort(s后面)第22頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五23C(n)=Cpartition(n)+CQuickSort(s前面)+CQuickSort(s后面)上式依賴(lài)于s的位置。考慮partition的基本操作：比較一次分區(qū)算法的比較次數(shù)是否和其他因素相關(guān)對(duì)于一次長(zhǎng)度為n的數(shù)組的分區(qū)算法，如果出現(xiàn)指針交叉，所執(zhí)行的比較是n+1次，為什么？相等，比較次數(shù)為n次第23頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五24整個(gè)算法的最壞情況下：在進(jìn)行了n+1次比較后建立了分區(qū)，還會(huì)對(duì)數(shù)組進(jìn)行排序，繼續(xù)到最后一個(gè)子數(shù)組A[n-2..n-1]。總比較次數(shù)為：Cworst(n)=(n+1)+n+…+3=(n+2)(n+1)/2-3∈Θ(n2)第24頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五25最好情況每次分區(qū)執(zhí)行n次并且每次都是等分Cbest(n)=2Cbest(n/2)+n∈Θ(nlog2n)第25頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五26平均情況分裂點(diǎn)有可能在一次分區(qū)后出現(xiàn)在每個(gè)位置設(shè)概率是1/n第26頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五274.1-4.2結(jié)論合并排序最差Θ(nlog2n)快速排序最優(yōu)Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)選擇排序 Θ(n2)冒泡排序 Θ(n2)第27頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五284.3折半查找(有序數(shù)組)位置：0123456789101112值：3,14,27,31,39,42,55,70,74,81,85,93,98K=70↑↑↑迭代1l=0m=6r=12迭代2lm=9r迭代3lr結(jié)果m=(7+8)/2=7第28頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五29

BinarySearch(A[0..n-1],k)//輸入：已排序大小為n的序列A，待搜索對(duì)象k//輸出：如果搜索成功，則返回k的位置，否則返回-1l=0,r=n-1;Whilel≤r mid=(l+r)/2 ifk=A[mid]returnmid elseifk<A[mid]r=m-1 elsel=m+1return-1

折半查找偽代碼第29頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五30折半查找效率分析：基本操作：比較

最壞情況下，比較次數(shù)C(n)=C(n/2)+1C(1)=1設(shè)n=2k，可解得

C(n)=k+1=log2n+1于是

C(n)∈Θ(log2n)第30頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五314.3結(jié)論折半查找最差Θ(log2n)順序查找 Θ(n)是一種退化了的分治法第31頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五324.4二叉樹(shù)遍歷及其相關(guān)特性所謂二叉樹(shù)的遍歷指的是遵循某一種次序來(lái)訪問(wèn)二叉樹(shù)上的所有結(jié)點(diǎn)，使得樹(shù)中每一個(gè)結(jié)點(diǎn)被訪問(wèn)了一次且只訪問(wèn)一次。由于二叉樹(shù)是一種非線性結(jié)構(gòu)，樹(shù)中的結(jié)點(diǎn)可能有不止一個(gè)的直接后繼結(jié)點(diǎn)，所以遍歷以前必須先規(guī)定訪問(wèn)的次序。第32頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五33中序遍歷（InorderTraversal）二叉樹(shù)的中序遍歷算法比較簡(jiǎn)單，使用遞歸的策略。在遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直接返回；否則中序遍歷的算法步驟如下：（1）對(duì)左子樹(shù)L執(zhí)行中序遍歷算法（2）訪問(wèn)輸出根結(jié)點(diǎn)V的值。（3）對(duì)右子樹(shù)R執(zhí)行中序遍歷算法。第33頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五34前序遍歷（PreorderTraversal）有了上面的中序遍歷的過(guò)程，前序遍歷也是類(lèi)似的。在遍歷以前首先確定遍歷的樹(shù)是否為空，如果為空，則直接返回；否則前序遍歷的算法步驟如下：（1）訪問(wèn)輸出根結(jié)點(diǎn)V的值；（2）對(duì)左子樹(shù)L執(zhí)行前序遍歷算法。（3）對(duì)右子樹(shù)R執(zhí)行前序遍歷算法。

第34頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五35前序遍歷執(zhí)行過(guò)程圖第35頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五36二叉樹(shù)的構(gòu)造第36頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五37二叉樹(shù)的高度計(jì)算算法Height(T)//輸入一棵二叉樹(shù)T//輸出二叉樹(shù)的高度//二叉樹(shù)高度定義：葉子到樹(shù)根的最長(zhǎng)路徑ifT=φreturn-1elsereturnmax{Height(L),Height(R)}+1例：計(jì)算上例中二叉樹(shù)的高度

H(T)=1+max{H(2),H(6)}=2+max{H(3),H(4)}=3+H(5)=5第37頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五384.5大整數(shù)乘法和Strassen矩陣乘法整數(shù)乘法問(wèn)題:設(shè)A和B為兩個(gè)N位的整數(shù)，計(jì)算它們的乘積A·B。思考按照通常做法要執(zhí)行一位乘法多少次？如：234×1251170468＋234*****N2次。第38頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五39分治法如何體現(xiàn)。令N為偶數(shù)，則A和B可表示為其中a1和a2分別為A的前半部和后半部。A＝a1·10N/2+a2(123456=123·106/2+456)B＝bl·10N/2+b2

bl

和b2則分別為B的前半部和后半部。如果按下述方法得到積(多項(xiàng)式相乘)A·B=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2第39頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五40A·B=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2估算時(shí)間效率是多少(即需要多少次一位乘法)？則要4次N/2位乘法，即N2次一位乘法。因此這種方法沒(méi)有改進(jìn)原來(lái)的方法。第40頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五41改進(jìn)的乘法A·B=(a110n/2+a2)(b110n/2+b2)=a1b110n+(a1b2+a2b1)10n/2+a2b2

=a1b110n+[(a1+a2)(b1+b2)-a1b1-a2b2)]10n/2+a2b2此時(shí)需要乘法多少次？這種方法需要3次n/2位的乘法及一些加減法。記C(n)為計(jì)算兩個(gè)n位整數(shù)相乘所需的基本操作執(zhí)行次數(shù)，則第41頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五42有

C(n)=3C(n/2)+k·nC(1)=1其中，k為常數(shù)，KN表示加法、減法所需時(shí)間與N成正比。解此遞歸方程，得

C(n)=nlog3+2knlog3-2kn∈O(nlog3)≈O(n1.58)可見(jiàn)，乘法效率有改善。第42頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五43評(píng)價(jià)其原理在于乘法操作所需時(shí)間比加法多得多，因此減少乘法次數(shù)，雖然代價(jià)為增加加法運(yùn)算，總的效果還是加速了運(yùn)算.大整數(shù)(500比特或1024比特)的乘法用于加密和認(rèn)證.第43頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五442、Strassen矩陣乘法矩陣乘法是線性代數(shù)中最常見(jiàn)的運(yùn)算之一，它在數(shù)值計(jì)算中有廣泛的應(yīng)用。若A和B是2個(gè)n×n的矩陣，則它們的乘積C=A×B同樣是一個(gè)n×n的矩陣。A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i,j]，加法和乘法的次數(shù)是多少？需要做n個(gè)乘法和n-1次加法。因此，求出矩陣C的n2個(gè)元素所需的計(jì)算時(shí)間為O(n3)。第44頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五45Strassen矩陣乘法如何對(duì)矩陣乘法采用分治？首先，假設(shè)n=2k。將矩陣A，B和C中每一矩陣都分塊成為4個(gè)大小相等的子矩陣，每個(gè)子矩陣都是n/2×n/2的方陣。由此可將方程C=A×B重寫(xiě)為:第45頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五46Strassen矩陣乘法其中：C11C12C21C22是多少？C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

第46頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五47

C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

依此算法，計(jì)算2個(gè)n階方陣的乘積轉(zhuǎn)化為計(jì)算8個(gè)n/2階方陣的乘積和4個(gè)n/2階方陣的加法上述分治法的計(jì)算時(shí)間耗費(fèi)T(n)如何寫(xiě)？T(n)=8T(n/2)+cn2

T(1)=1計(jì)算T(n)是多少？這個(gè)遞歸方程的解仍然屬于O(n3)

第47頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五48Strassen方法

M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)他的算法只用了7次乘法運(yùn)算，但增加了加、減法的運(yùn)算次數(shù)10次。觀察使用了多少次乘法?加減法用了多少次？第48頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五49于是可得到:

C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7引入8次加減法Strassen矩陣乘積分治算法中，用了7次對(duì)于n/2階矩陣乘積的遞歸調(diào)用和18次n/2階矩陣的加減運(yùn)算。由此可知，該算法的所需的計(jì)算時(shí)間T(n)滿(mǎn)足如下的遞歸方程:

第49頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五50Strassen矩陣乘法

其解為T(mén)(n)∈O(nlog7)≈O(n2.81)。由此可見(jiàn)，Strassen矩陣乘法的計(jì)算時(shí)間復(fù)雜性比普通矩陣乘法有階的改進(jìn)。T(n)=7T(n/2)+kn2

T(1)=1第50頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五51結(jié)論大整數(shù)乘法和矩陣乘法分別利用了將乘法轉(zhuǎn)換為多個(gè)加法進(jìn)行替代。對(duì)于矩陣乘法可以將矩陣作3×3的劃分，即將矩陣分成九個(gè)子矩陣，或作4×4的劃分(即將矩陣分成十六個(gè)子矩陣)。相應(yīng)地要求矩陣的階n是3的整次冪(或4的整次冪)。有人沿這個(gè)途徑改善了矩陣乘法的復(fù)雜度。第51頁(yè)，共62頁(yè)，2022年，5月20日，15點(diǎn)25分，星期五524.6分治法解最近點(diǎn)對(duì)問(wèn)題和凸包問(wèn)題問(wèn)題:給定平面S上n個(gè)點(diǎn),找其中的一對(duì)點(diǎn),使得在n(n-1)/2個(gè)點(diǎn)對(duì)中,該點(diǎn)對(duì)的距離最小。算法思路:1)n較小時(shí)直接求(n=2).2)將S上的n個(gè)點(diǎn)分成大致相等的2個(gè)子集S1和S23)分別求S1和S2中的最接近點(diǎn)對(duì)

4)求一點(diǎn)在S1、另一點(diǎn)在S2