【文章內(nèi)容簡介】 T(n/2) ≤a(n/2)log(n/2)+b 帶入原式： T(n) ≤2T(n/2)+c2n≤2(a(n/2)log(n/2)+b)+c2n =an(logn1)+c2n+2b =anlogn+b(anc2nb) 只要令 anc2nb≥0就有 T(n) ≤anlogn+b 選擇 a≥c2+b，使 anc2nb≥0得到滿足。 使 T(n) ≤anlogn+b成立的兩個約束是： b≥c1， a≥c2+b 取 b=c1 , a=c1+c2 是合理的。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 20 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 一類遞歸方程的展開式與通解 設(shè) T(n)是求解某個問題的時間開銷， n使問題的數(shù)據(jù)量。設(shè)計(jì) 對此問題列出的遞歸方程為： T(1)=1 T(n)=aT(n/c)+d(n) n≥2 其中 c是大于等于 1的正整數(shù)。全部數(shù)據(jù)被分割成 c等分，每分的 數(shù)量為 n/c。 T(n/c)是求解一個子問題的時間開銷。 aT(n/c)代表求 解 a個問題的時間開銷。 D(n)是任意的函數(shù)，方程是嚴(yán)格的等式。 用 n/ci代替 n得： T(n/ci)=aT(n/ci+1)+d(n/ci), i=1,2,3,… T(n)=aT(n/c)+d(n) =a(aT(n/c2)+d(n/c))+d(n)=a2T(n/c2)+ad(n/c)+dn =a2(aT(n/c3)+d(n/c2))+ad(n/c)+d(n) =a3T(n/c3)+a2d(n/c2)+ad(n/c)+d(n) =…… =ai T(n/ci)+∑ajd(n/cj) i1 j=0 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 21 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 T(n)=ai T(n/ci)+∑ajd(n/cj) i1 j=0 假設(shè) n=ck，則 T(n/ck)=T(1)=1, 令 i=k 有： T(n)= ak+∑ajd(ckj) 利用 k=log，則上式第一項(xiàng)可寫成 alogc 或等價于 nlogc k1 j=0 n a 齊次解與特解： 當(dāng) d(n)=0時， ak或 alogc 稱為方程的齊次解。 n 倍積函數(shù)： 若對所有的正整數(shù) x， y，有 f(xy)=f(x)f(y)，則 f 是 正整數(shù)上的倍積函數(shù)。 若 d(n)是倍積函數(shù)。則有： d(ck1)=(d(c))k1 ∑ajd(ck1)=∑aj(d(c))k1 =(d(c))k∑(a/d(c))j =(ak(d(c))k)/(a/d(c)1) k1 j=0 k1 j=0 k1 j=0 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 23 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 定理： 設(shè) a,c是非負(fù)常數(shù)， n是 2的冪， d(n)是倍積函數(shù)，則 T(n) = b n=1 aT(n/c)+d(n) n1 的齊次解是 O(nlogc )，且對特解有如下結(jié)論： (1)若 ad(c)，則特解是 O(ak)，或 O(nlogc ),即特解與齊次解同階 (2)若 ad(c)，則特解是 O((d(c)k)，或 O(nlogcd(c))即特解與 d同階 (3)若 a=d(c)，則特解是齊次解的 log。 a a . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 24 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 基本思想：分而治之。將一個規(guī)模為 n的問題分解為 k個規(guī)模較小 的子問題，這些子問題互相獨(dú)立且與原問題相同。遞 歸地解這些子問題，然后將各子問題的解合并得到原 問題的解。 設(shè)問題輸入數(shù)據(jù) A[0..n1]，函數(shù) dac(p,q)求子問題 A[p,q]的解。 對函數(shù) dac的首次調(diào)用是 dac(0,n1)。 int dac(int p, int q) { if(small(p,q)) return(G(p,q))。 else { (m1,…,m k)=divide(p,q)。 return(Combine(dac(p,m1),dac(m1+1,m2),…, …,dac(m k+1,q))。 } } 分治方法與軟件設(shè)計(jì)的模塊化方法非常相似。為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別解決每個小問題； 3) 把各小問題的解組合起來，即可得到原問題的解答。 小問題通常與原問題相似，可以遞歸使用分治策略來解決。 ?分治 （ Divide and Conquer ） . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 25 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 整數(shù)乘法 求兩個 n位數(shù)之積，傳統(tǒng)方法需要 O(n2)次比較運(yùn)算，運(yùn)用分治 法可以將運(yùn)算次數(shù)的階降到 O(nlog3) ≈O()。 設(shè) x和 y都是 n位數(shù)， n是 2的冪，將 x和 y各分成兩半，每一半都 是 n/2位數(shù)，則 xy的積可寫成： xy=(a2n/2+b) (c2n/2+d) =ac2n+(ad+bc) 2n/2+bd 也可寫成： xy=ac2n+[ac+ (ab) (dc) +bd)] 2n/2+bd a b c d x= y= . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 26 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 int mult(int x, int y,int n) { if(n=1) return(x*y)。 else { s=sign(x)*sign(y)。 x=abs(x)。 y=abs(y)。 a=x的左 n/2位； b=x的右 n/2位； c=y的左 n/2位； d=y的右 n/2位； v=mult(a,c,n/2)。 u=mult(ab,dc,n/2)。 w=mult(b,d,n/2)。 return(s*(v*2n+(u+v+w)*2n/2+w)) } } T(n)= k n=1 3T(n/2)+kn n1 算法分析： T(n)=O(nlog3) 解： T(n)=3knlog32kn . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 27 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 例：設(shè) x=3141, y=5327, 利用分治法求 xy 31 41 53 27 x= y= x=3141 a=31 b=41 ab=10 y=5327 c=53 d=27 dc=26 ac=(1643)*, bd=(1107)*, (ab) (dc)=(260)* xy=ac104+(ac+(ab) (dc)+bd) 102+bd =(1643)*104+[(1643)*+(260)*+(1107)*] 102+(1107)* =(16732107)* a=31 a1=3 b1=1 a1b1=2 c=53 c1=5 d1=3 d1c1=2 a1c1=15, b1d1=3, (a1b1) (d1c1)=4 ac=15102+(15+34)101+3=1632 b=41 a2=4 b2=1 a2b2=3 d=27 c2=2 d2=7 d2c2=5 a2c2=8, b2d2=7,