第二章算法设计与分析的基本方法及技巧

第二章算法设计与分析的基本方法及技巧内容摘要：

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 是合理的。 . 算法与数据结构 Slides. 2 20 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 一类递归方程的展开式与通解 设 T(n)是求解某个问题的时间开销， n使问题的数据量。 设计 对此问题列出的递归方程为： T(1)=1 T(n)=aT(n/c)+d(n) n≥2 其中 c是大于等于 1的正整数。 全部数据被分割成 c等分，每分的 数量为 n/c。 T(n/c)是求解一个子问题的时间开销。 aT(n/c)代表求 解 a个问题的时间开销。 D(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 . 算法与数据结构 Slides. 2 21 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 T(n)=ai T(n/ci)+∑ajd(n/cj) i1 j=0 假设 n=ck，则 T(n/ck)=T(1)=1, 令 i=k 有： T(n)= ak+∑ajd(ckj) 利用 k=log，则上式第一项可写成 alogc 或等价于 nlogc k1 j=0 n a 齐次解与特解： 当 d(n)=0时， ak或 alogc 称为方程的齐次解。 n 倍积函数： 若对所有的正整数 x， y，有 f(xy)=f(x)f(y)，则 f 是 正整数上的倍积函数。 若 d(n)是倍积函数。 则有： 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 . 算法与数据结构 Slides. 2 23 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 定理： 设 a,c是非负常数， n是 2的幂， d(n)是倍积函数，则 T(n) = b n=1 aT(n/c)+d(n) n1 的齐次解是 O(nlogc )，且对特解有如下结论： (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 . 算法与数据结构 Slides. 2 24 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 基本思想：分而治之。 将一个规模为 n的问题分解为 k个规模较小 的子问题，这些子问题互相独立且与原问题相同。 递 归地解这些子问题，然后将各子问题的解合并得到原 问题的解。 设问题输入数据 A[0..n1]，函数 dac(p,q)求子问题 A[p,q]的解。 对函数 dac的首次调用是 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))。 } } 分治方法与软件设计的模块化方法非常相似。 为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解组合起来，即可得到原问题的解答。 小问题通常与原问题相似，可以递归使用分治策略来解决。 分治 （ Divide and Conquer ） . 算法与数据结构 Slides. 2 25 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 整数乘法 求两个 n位数之积，传统方法需要 O(n2)次比较运算，运用分治 法可以将运算次数的阶降到 O(nlog3) ≈O()。 设 x和 y都是 n位数， n是 2的幂，将 x和 y各分成两半，每一半都 是 n/2位数，则 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= . 算法与数据结构 Slides. 2 26 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 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 . 算法与数据结构 Slides. 2 27 第二章 算法设计与分析的基本方法与技巧 国家示范性软件学院 2020 秋 例：设 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,。