引论-递归与分治

1、 算法设计与分析算法设计与分析 Design and Analysis of Computer AlgorithmDesign and Analysis of Computer Algorithm刘云华刘云华 王波兴王波兴2参考教材 王晓东 算法设计与分析（第2版），清华大学出版社，2008 周培德 计算几何算法分析与设计（第2版） 清华大学出版社，2005第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法第八章第八章 NP

2、NP完全性理论简介完全性理论简介算法设计与分析算法设计与分析 目录目录算算 法法 概概 述述Algorithm IntroductionAlgorithm Introduction第一章第一章介绍算法设计的基本概念介绍算法设计的基本概念及算法分析的方法和准则及算法分析的方法和准则.算法设计与分析算法设计与分析5一系列将问题的输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。 2. 计算机算法与人工算法计算机算法与人工算法 算法设计与分析算法设计与分析 算法概述算法概述1.1 算法 AlgorithmAlgorithm1. 算法定义算法定义 有些问题没有计算机算法有些问

3、题没有计算机算法. . 有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同. . 2).确定性 definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义, ,对每种可能的情况对每种可能的情况, ,算法都算法都 要给出确定的操作要给出确定的操作. . 1).有穷性 finiteness 算法必须在执行有穷步后终止算法必须在执行有穷步后终止, ,且每一步均在有限时间内完成且每一步均在有限时间内完成 3).能行性effectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的, ,算法执行结果要达到预期目的算法执行结果要达到预期目的 3

4、.3.计算机算法的一般特征计算机算法的一般特征 4).有有0 0个或多个输入项个或多个输入项, ,至少有一个输出项至少有一个输出项. .6算法设计与分析算法设计与分析 算法概述算法概述数值型算法数值型算法: :算法中的基本运算为算术运算算法中的基本运算为算术运算. .非数值型算法非数值型算法: :算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算. .串行算法串行算法: :串行计算机上执行的算法串行计算机上执行的算法. .并行算法并行算法: :并行计算机上执行的算法并行计算机上执行的算法. .从处理方式上从处理方式上6. 算法分类算法分类从解法上从解法上5.算法描述语言 1).数据数据: 运

5、算序列中作为运算对象和结果的数据运算序列中作为运算对象和结果的数据. . 2).运算运算: 运算序列中的各种运算运算序列中的各种运算: :赋值赋值, ,算术和逻辑运算算术和逻辑运算 3).控制和转移控制和转移: 运算序列中的运算序列中的控制和转移控制和转移. . 4. .算法的三个要素自然语言自然语言, ,数学语言数学语言, ,流程图流程图, ,程序设计语言等等程序设计语言等等. .7算法设计与分析算法设计与分析 算法概述算法概述7.问题的求解过程2)建立数学模型(UML)1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言用科学规范的语言, ,对所求解

6、的问题做准确的描述对所求解的问题做准确的描述. .通过对问题的分析通过对问题的分析, ,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述. .根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法. .证明算法对一切合法输入均能在有限次计算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出. .对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算. .将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序. .8算法设计与分析算法设计与分析 算法概述算法概

7、述1.2 1.2 算法复杂性分析算法复杂性分析1.复杂性的计量k1I)(N,etiii显然显然, ,它与问题的规模它与问题的规模, ,算法的输入数据及算法本身有关算法的输入数据及算法本身有关. . 将时间复杂性和空间复杂性分别考虑将时间复杂性和空间复杂性分别考虑, ,并用并用T T和和S S表示表示. .则则 T=T(N,I,A) S=S(N,I,A)T=T(N,I,A) S=S(N,I,A) 将将A A隐含在函数名中隐含在函数名中, ,则则 T=T(N,I,A) T=T(N,I,A) 简化为简化为T=T(N,I)T=T(N,I) 算法的复杂性:算法执行所需的时间和空间的数量算法执行所需的时间

8、和空间的数量. .令令 NN: :问题的规模问题的规模 I I: :输入数据输入数据 A A: :算法本身算法本身 则算法的复杂性则算法的复杂性 C=F (N,I,A)C=F (N,I,A)设一台抽象计算机提供的元运算有设一台抽象计算机提供的元运算有k k种种, ,分别记作分别记作O O1 1 ,O,Ok k 设这些元运算每执行一次所需时间分别为设这些元运算每执行一次所需时间分别为t t1 1 , , t t2 2,t,tk k , ,设算法设算法A A中用到中用到O Oi i的次数为的次数为 e ei i, , i i=1,=1,k k, ,则则 e ei i= = e ei i(N,I(N

9、,I ) T=T(N,I)= T=T(N,I)= 9算法设计与分析算法设计与分析 算法概述算法概述 算法的复杂性最好情况最好情况: :T Tminmin(N) = T(N,I) = (N) = T(N,I) = = = = =最坏情况最坏情况:T:Tmaxmax(N) = T(N,I) =(N) = T(N,I) = = = = = 平均情况平均情况:T:Tavgavg(N) = = (N) = = kiiiINet1)(, ,kiiiINet1)(, ,kiiiINet1)( , ,)(INT , ,NDIm inm inkiiiINet1)(, ,NDIm axm axkiiiINet1)

10、(* *, ,NDIIPI)T(N,)()(* *, ,INTnDIIP)(NDIm inm inNDIm axm axI I 例例 题题1-1其中其中 D DNN: :规模为规模为NN的所有合法输入的集合的所有合法输入的集合 I I* *: D: DNN中达到中达到T Tmax max (N)(N)的一个输入的一个输入 : D: DNN中达到中达到T Tmin min (N)(N)的一个输入的一个输入 P(I): P(I): 出现输入为出现输入为I I的概率的概率算法设计与分析算法设计与分析 已 知 不 重 复 且 从 小 到 大 排 列 的已 知 不 重 复 且 从 小 到 大 排 列 的

11、 mm 个 整 数 的 数 组个 整 数 的 数 组 A 1 . . . m , m = 2A 1 . . . m , m = 2K K, K, K为 正 整 数为 正 整 数 . . 对 于 给 定 的 整 数对 于 给 定 的 整 数 c ,c , 要 求 找 到 一 个 下 标要 求 找 到 一 个 下 标 i ,i , 使 得使 得 A i = c .A i = c . 找 不 到 返 回找 不 到 返 回 0 .0 .function search(c) i:=1; a while Aic and i=L do t (logm+2) i:=(L+U)div2; (a+s+d)(log

12、m+1) if c=Ai t (logm+1)then found:=true aelse if cAi t (logm+1) then L:=i+1 (s+a)(logm+1) else U:=i-1 if found a then b-search:=i else b-search:=0 a 在数学上在数学上, ,T(T(n n) )与与 有相同的最高阶项有相同的最高阶项. .可取可取 为略去为略去T(T(n n) )的的低阶项后剩余的主项低阶项后剩余的主项. .当当n n充分大时我们充分大时我们用用 代替代替T(T(n n) )作为算法复杂性的度量作为算法复杂性的度量, ,从而简化分析从

13、而简化分析. .设设T(T(n n) )为算法为算法A A的时间复杂性函数的时间复杂性函数, ,则它是则它是n n的单增函数的单增函数, ,如果存在一个函数如果存在一个函数 使得当使得当n n , ,有有 (T(T(n n)- ) / T()- ) / T(n n) )0 0称称 是是T(T(n n) )当当 n n 时的时的渐进性态或或 渐进复杂性. .12算算法设计与分析分析 算法概述算法概述 算法的复杂性2 复杂性的渐进性态 1).渐进性态)(T n )(nT T )(nT T )(nT T )(nT T )(nT T )(T n )(T n 例如例如 T(n)=3n2+4nlogn+7

14、, 则则 可以是3n2. 若进一步假定算法中所有不同元运算的单位执行时间相同若进一步假定算法中所有不同元运算的单位执行时间相同, ,则可不考虑则可不考虑 所包含的系数或常数因子所包含的系数或常数因子。渐进分析适用于渐进分析适用于n n充分大的情况充分大的情况, ,当问题的规模很小时当问题的规模很小时, ,或比较的两算法同阶时或比较的两算法同阶时, ,则不能做这种简化则不能做这种简化. .13算算法设计与分析分析 算法概述算法概述 算法的复杂性2).2).渐进性态的阶又如算法又如算法1-11-1中中Tmin (m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,Tmin

15、 (m)=O(1)Tmax(m)=O(m)例如例如3n=O(n),n+1024=O(n),n2=O(n3) ?n3=O(n2) ?2n2+11n-10=O(n2) 若 存 在 正 常 数若 存 在 正 常 数c c和 自 然 数和 自 然 数NN0 0 使 得 当使 得 当 N N NN0 0 时时 , , 有有 f (f (NN) ) c g c g ( (NN) ) 则 称 函 数则 称 函 数 f (f (NN ) ) 在在NN充 分 大 时 有充 分 大 时 有 上 界上 界 , , 且且 g g( (NN) ) 是 它 的 一 个 上 界是 它 的 一 个 上 界 , , 记 为记

16、为 f (f (NN) = O () = O (g g ( (NN) ) ) , , 也 称也 称 f (f (NN) ) 的的 阶阶 不 高 于不 高 于g g ( (NN) ) 的的 阶阶 . . 设设f(N)f(N)和和 g g (N) (N) 是定义在正整数集上的正函数是定义在正整数集上的正函数, ,(1)大大O O表示法表示法 (算法运行时间的上限 )14算算法设计与分析分析 算法概述算法概述 算法的复杂性例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性T(n2)T(n2)的阶的阶. .分析:内循环体只需O(1)时间,故for i:= 1

17、 to n do for j:=1 to i do s1,s2,s3,s4 ; s1,s2,s3,s4为单一赋值语句ij 1O(1)O()1O(1iij外循环共需)O(N)21O()O()O(21N1) )( (NNiiNii 1. O(f)+O(g)=O(max(f,g)1. O(f)+O(g)=O(max(f,g) 2. O(f)+O(g)=O(f+g) 2. O(f)+O(g)=O(f+g) 3. O(f)O(g)=O(fg) 3. O(f)O(g)=O(fg) 4. 4. 如果如果 g(n)=O(f(n),g(n)=O(f(n),则则 O(f)+O(g)=O(f) O(f)+O(g)=

18、O(f) 5. f=O(f) 5. f=O(f) 6. O(cf(n)=O(f(n) 6. O(cf(n)=O(f(n)运算法则内循环共需 15算算法设计与分析分析 算法概述算法概述 算法的复杂性(2)大表示法 (算法运行时间的下限） f(N) =f(N) = ( (g g(N)(N) ) ) 当且仅当当且仅当 f(N) =O(f(N) =O(g g (N)(N) ) ) 且且f(N)=f(N)= ( (g g (N)(N) ) ) 称函数称函数f(N)f(N)与与g g (N)(N)同阶同阶. .算法的渐进复杂性的阶对于算法的效率有着决定性的意义算法的渐进复杂性的阶对于算法的效率有着决定性的

19、意义: :多项式阶算法多项式阶算法( (有效算法有效算法):):时间复杂性与规模时间复杂性与规模N N 的幂同阶的幂同阶. .指数阶算法指数阶算法: :时间复杂性与规模时间复杂性与规模N N 的一个指数函数同阶的一个指数函数同阶. .最优算法最优算法: :时间复杂性达到其下界的算法时间复杂性达到其下界的算法. .如果如果 正常数正常数c c和自然数和自然数NN0 0使得当使得当 N N NN0 0 时时, , 有有f(N)f(N) c cg g (N) (N) 则称函数则称函数f(N)f(N)在在NN充分大时有充分大时有下限下限, , 且且 g g(N)(N)是它的一个下限是它的一个下限, ,

20、记为记为f(N) = f(N) = ( (g g (N) ) (N) ) 也称也称f(N)f(N)的的阶阶不低于不低于g g(N)(N)的的阶阶。(3)表示法16算算法设计与分析分析 算法概述算法概述 算法的复杂性图1 时间函数的增长率常见的多项式阶有常见的多项式阶有:O(1)O(1)O(logn)O(logn)O(n)O(n)O(nlogn)O(nlogn)O(nO(n2 2)O(nO(n3 3) )O(2O(2n n)O(n!)O(n!) 算法概述算法概述 算法的复杂性 3.渐进分析 时间复杂性渐进阶分析的规则:(最坏情况) 1). 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需

21、1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1；a2: s2；.； am: sm 需要的时间为 max（TS1,TS2 ,., TSm）. 4). 访问数组的单个分量或纪录的单个域需要一个单位时间一个单位时间. 5). 执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数循环次数. 7). 用goto从循环体内跳到循环体末或循环后面的语句时,不需

22、额外时间 8). 过程或函数调用语句 对非递归调用,根据调用层次由里向外用规则1-7进行分析； 对递归调用,可建立关于T(n)的的递归方程,求解该方程得到T(n). 例例 题题1-1算法设计与分析算法设计与分析 算法1-2:二分查找 (假定c是A的最后一元)例例 题题 1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t, 加法s, 除法d, 减法b.最坏情况Tmax(m) = 8a+4t+2s+d+(2a+2s+3t+d) logm=14+8logmfunction b-search(c) L:=1; U:=m; 2 found:=false; 1 while not found an

23、d U=L do Logm+2 i:=(L+U)div2; 3 if c=Ai 1then found:=true （ 1）else if cAi 1 then L:=i+1 2 else U:=i-1 if found 1 then b-search:=i else b-search:=0 1 Logm+1算法设计与分析算法设计与分析 已知不重复且从小到大排列的m个整数的数组A1.m,m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得Ai=c.找不到返回0.例例 题题 1-1function b-search(c,L,U) if Uc then 1 b-search:= b-s

24、earch(c,L, index-1); 3+T(m/2) else b-search:= b-search(c,index+1,U); 3+T(m/2) ; 设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2 2 m=m=0 013 13 m=1m=1 11+T(11+T(mm/2) /2) m1m1T(m)=T(m)=解得: T(m) =11logm+13= (logm)算法1-3:二分查找递归算法算法设计与分析算法设计与分析 求Fibonacci数列的前N项 a a0 0, a, a1 1, a, aNN 其中, a0=0, a1=1, a ai i=

25、a= ai-1i-1+ + a ai-2i-2算法1-4Procedure seq(n) function A(n) if n=0 then 1 A:=0 1 else if n=1 then 1 A:=1 1 else A:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2) ; if n1 n1F(n)=F(n)=ni0例例 题题 1-2ni021算算法设计与分析分析 算法概述算法概述 算法的复杂性4).套用公式法 若递归方程形如:T(n)=aT(n/b)+ f(n),可根据f(n)的不同情况套用公式 1)若0,使得 f(n)=O(n logb b a-),则T(n)=(n log

26、b b a) 2)若f(n)=(n logb b a), 则T(n)=(n logb b a logn) 3)若0,使得f(n)=(n logb b a+),且 c 递归与分治递归与分治第二章 递归与分治(Divide and Conquer)2.1 递归的概念例1. 阶乘函数 f(n) =n!=n*(n-1)*(n-2)*3*2*1 =n*(n-1)! =n*f(n-1)int factorial(int n)int f;if(n=0) f=1;else f =n* factorial(n-1); /调用自身函数调用自身函数return f;直接或间接地调用自身的算法称为递归算法直接或间接地

27、调用自身的算法称为递归算法. .23算算法设计与分析分析 递归与分治递归与分治Class Factorial public int n, f; Factorial(m) n=m; f=1; ;int factorial(int n) Factorial *p; for(int i=n; i0; i-) p=new Factorial(i); PushStack(p); Factorial *CurOb; Popup(&CurOb); while( Stack is not empty) Popup(&p); p.f=p.n* CurOb.f; delete CurOb; Cur

28、Ob=p; return CurOb.f;递归程序的栈实现递归程序的栈实现24算算法设计与分析分析 递归与分治递归与分治Fibonacci 数列: F(n)=F(n-1)+F(n-2), F(0)=F(1)=1递归代表一种计算规则递归代表一种计算规则, 有时有函数表示结果有时有函数表示结果,有时没有有时没有.1125125151)(nnnF整数划分问题整数划分问题 n=n1+n2+nk, 划分数划分数p(n)计算的递归方法计算的递归方法有函数表有函数表示示无函数表无函数表示示25算算法设计与分析分析 递归与分治递归与分治例例5 5 整数划分问题整数划分问题将正整数将正整数n n表示成一系列正整

29、数之和：表示成一系列正整数之和：n=n1+n2+n=n1+n2+nk+nk，其中其中n1n2n1n2nk1nk1，k1k1。正整数正整数n n的这种表示称为正整数的这种表示称为正整数n n的划分。求正整数的划分。求正整数n n的不的不同划分个数。同划分个数。 例如正整数例如正整数6 6有如下有如下1111种不同的划分：种不同的划分： 6 6； 5+15+1； 4+24+2，4+1+14+1+1； 3+33+3，3+2+13+2+1，3+1+1+13+1+1+1； 2+2+22+2+2，2+2+1+12+2+1+1，2+1+1+1+12+1+1+1+1； 1+1+1+1+1+11+1+1+1+1

30、+1。26算算法设计与分析分析 递归与分治递归与分治(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1 的划分组成。(3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。例5 整数划分问题在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。27算算法设计与分析分析 递归与分治递归与分治11, 1),() 1,() 1,(1),(1),(mnmnmnmn

31、mmnqmnqnnqnnqmnq例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。 m=n的划分只有一个最大加数达是m的划分个数等于将m从n中减去后n-m中最大加数是m的划分个数28例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一

32、起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。29算算法设计与分析分析 递归与分治递归与分治递归代表一种计算规则递归代表一种计算规则, 有时其计算出的实现过程很难人工模拟有时其计算出的实现过程很难人工模拟.用已知方法将上用已知方法将上n-1盘盘, 从从a移到移到ccabvoid Hanoi (int n, int a, int b, int c) if(

33、n0) Hanoi(n-1, a, c, b); move(a,b); Hanoi(n-1,c, b, a); 设对于任意设对于任意n,n,方法已知方法已知( (实际未知实际未知) )将第将第n盘盘, 从从a移到移到b用已知方法将上用已知方法将上n-1盘盘, 从从c移到移到b优点：优点：结构清晰，可读性强，而且容易用数学归纳法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费

34、的计算时间还是占用的存储空间都比非递归算法要多。非递归算法要多。算算法设计与分析分析 递归与分治递归与分治解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消除递归调用，使其转化为非递归算法。化为非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化，只不过人工做了本来由编译器做的事情，优化效果不明显。效果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过、通过变换能变换能将一些递归转化为

35、非递归，从而将一些递归转化为非递归，从而迭代求出结果。迭代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。算算法设计与分析分析 递归与分治递归与分治32算算法设计与分析分析 递归与分治递归与分治2.2 分治(Divide and Conquer)基本思想 Divide-and-Conquer(P) if ( |P|=n0) Adhoc(P); 直接求解问题 P divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i 递归与分治递归与分治设问题P(n)分

36、解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:)f(n/mknT(n)1nogl0klogmmjjj T(n)= 算法的时间复杂性 Divide-and-Conquer(P) if ( |P|=n0) Adhoc(P); divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i = k; i+) yi=Divide-and-Conquer(Pi); return Merge( yl ,.,

37、 yk); f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换, 棋盘覆盖,排序,选择 等.O(1)34)f(n/mknT(n)1nogl0klogmmjjjT(1)=1T(n)=2T(n/2)+2nT(n)=2 2T(n/22)+2*n/2 + 2n = 22T(n/22)+2*2n= 222T(n/23)+2n/22+ 2*2n =23T(n/23)+ 3*2n= = 2hT(n/2h)+ h*2n, 当h=log2n, 即2h=n时,=nT(1)+ 2nlog2n= n+ 2nlog2n=O(nlog2n)nogl(

38、nogl212n2nn/2*2*2nT(n)221nogl01nogl01nogl0222nOnnnnjjjjj当当k=m=2,f(n)=2n k=m=2,f(n)=2n 时时, ,验证此公式验证此公式: :算法设计与分析算法设计与分析 已 知 不 重 复 且 从 小 到 大 排 列 的已 知 不 重 复 且 从 小 到 大 排 列 的 mm 个 整 数 的 数 组个 整 数 的 数 组 A 1 . . . m , m = 2A 1 . . . m , m = 2K K, K, K为 正 整 数为 正 整 数 . . 对 于 给 定 的 整 数对 于 给 定 的 整 数 c ,c , 要 求

39、找 到 一 个 下 标要 求 找 到 一 个 下 标 i ,i , 使 得使 得 A i = c .A i = c . 找 不 到 返 回找 不 到 返 回 0 .0 .function search(c) i:=1; 1 while Aic and im do i:=i+1; (3+2)m if Ai=c then search:=i; else search:=0; 1+1算法1-1:顺序查找例例 题题 1-1最好情况Tmin (m)=4,最坏情况Tmax(m) =3+5m,Tmin (m)=O(1)Tmax(m) =O(m)/i:=1, A1amiddle) left=middle+1;

40、 /3 else right=middle-1; return binarySearch(a, x, left, right); 二分搜索算法二分搜索算法: :规模缩小为规模缩小为1/2, 1/2, 所以所以m=2,m=2,细化分枝为细化分枝为1,1,所以所以k=1.k=1.f(n)=7Log21=0T(n)=n0+7log2n= 1+7log2n=O(log2n)算法设计与分析算法设计与分析 算法1-2:二分查找例例 题题 1-1最坏情况Tmax(n) =O(logn)function b-search(c) L:=1; U:=n; found:=false; while not found

41、 and U=L do 3(logn+1) i:=(L+U)div2; 3(logn+1) if c=Ai logn+1then found:=true else if cAi logn+1 then L:=i+1 else U:=i-1 2(logn+1) if found then b-search:=1 else b-search:=0 n=2hh=logn38算法设计与分析算法设计与分析 递归与分治递归与分治2.4 大整数的乘法 设计一个有效的算法，可以进行两个设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的方法：O(n2) 效率太低u分治法: X =

42、 Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd abcd复杂度分析复杂度分析T(n)=O(n2) 没有改进没有改进11)()2/(4) 1 ()(nnnOnTOnT39算法设计与分析算法设计与分析 递归与分治递归与分治2.4 大整数的乘法XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。1.XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd2.XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd细节问题

43、细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。复杂度分析复杂度分析T(n)=O(nlog3) =O(n1.59) 较大的改进较大的改进11)()2/(3) 1 ()(nnnOnTOnT算法设计与分析算法设计与分析 递归与分治递归与分治2.4 大整数的乘法更快的方法更快的方法如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。算法设计与分析算法

44、设计与分析 递归与分治递归与分治 S=SIGN(X)*SIGN(Y)； X:=ABS(X)；Y:=ABS(Y)； if n=l then if (X=1) and (Y=1) then return(S) else return(0) else A:=X的左边n/2位； B:=X的右边n/2位； C:=Y的左边n/2位； D:=Y的右边n/2位； m1:=MULT(A，C，n/2)； m2:=MULT(A-B,D-C，n/2)； m3:=MULT(B，D，n/2)； S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)； return (S) X,Y为2个小于2n的二进制整数，返回结

45、果为X和Y的乘积XYfunction MULT(X,Y,n)大数相乘的分治递归算法大数相乘的分治递归算法二进制大整数乘法同样可应用于十进制大整数的乘法存放XY的符号存放三个乘积算法算法A和B的乘积矩阵C中的元素Ci,j定义为: nkjkBkiAjiC1若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：222112112221121122211211BBBBAAAACCCC由

46、此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3)22)()2/(8) 1 ()(2nnnOnTOnT为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMM

47、MC复杂度分析复杂度分析T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进22)()2/(7) 1 ()(2nnnOnTOnT 验证:C22 = M5+M1-M3-M7 = (A11+A22)(B11+B22) +A11 (B12-B21) -(A21+A22) B11 - (A11-A21)(B11+B12) =A11B11+A11B22+A22B11+A22B22+A11B12 -A11B22- A21B11 - A22B11 - A11B11 - A11B12+A21B11+A21B12 =A21B12+A22B22算法设计与分析算法设计与分析procedure STR

48、ASSEN(n,A,B,C)； if n=2 then MATRIX_MULTIPLY(A,B,C) else 将矩阵A和B分块； STRASSEN( n/2，A11，B12-B22，M1)； STRASSEN( n/2，A11+A12，B22，M2)； STRASSEN( n/2，A21+A22，B11，M3)； STRASSEN( n/2，A22，B21-B11，M4)； STRASSEN( n/2，A11+A22，B11+B22，M5) STRASSEN( n/2，A12-A22，B21+B22，M6)； STRASSEN( n/2，A11+A21，B11+B12，M7)73154321

49、6245MMMMMMMMMMMMC:=矩阵相乘Strassen算法 T(n)= T(2)= O(1)T(n)= 7T(n/2)+18(n/2)2 得: T(n)=O(nlog7)=O(n2.81) 分析: 算法算法/18/18次小矩阵相加次小矩阵相加u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)

50、的算法？47问 题 陈 述 : 在 一 个 2k 2k个 方 格 组 成 的 棋 盘 中 , 恰 有 一 方 格 残 缺 残 缺 方 格 的 位 置 有 22 k种 。 故 对 任 何 k 0 , 残 缺 棋 盘 有 22 k种 . 要 求 用 L 型 骨 牌 覆 盖 残 缺 棋 盘 上 的 所 有 方 格 且 任 何 2 个 L 型骨牌不得重叠覆盖。2k 2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/32.6 棋盘覆盖算法设计与分析算法设计与分析 递归与分治递归与分治48分治算法: 当k0时,将2k 2k棋盘分割为4个2k-1 2k-1子棋盘 残缺方格必位于4个子棋盘之一其余3个子棋盘中无

51、残缺方格为 此 将 剩 余 3 棋 盘 转 化 为 残 缺棋 盘 . 用 一 个 L 型 骨 牌 覆 盖 这3个较小棋盘的结合处.这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1 1棋盘.算法分析:设T(k)为覆盖2k 2k残缺棋盘的时间, 当k=0时覆盖它需要常数时间O(1)当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k-1) , T(k)= O(1)4T(k-1)+ O(1) 得: T(k)=(4k)与所需骨牌数同阶算法设计与分析算法设

52、计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 void ChessBoard(int tr, int tc, int dr, int dc, int size) if (size=1) return；/tr, tc : Corner row & column no. /dr,dc :特殊方格位置 int t=tile+，/ L型骨牌号 s=size2； / 分割棋盘 /覆盖左上角子棋盘覆盖左上角子棋盘 if (dr tr +s & dc tc +s) /特殊方格在此棋盘中 ChessBoard(tr，tc，dr，dc，s)； else/此棋盘中无特殊方格 /用t号

53、L型骨牌覆盖右下角 Boardtr+s-1tc+s-1=t； /覆盖其余方格 Chessboard(tr，tc，tr+s-1，tc+s-l，s)； (tr, tc)(dr, dc)size(tr, tc)(dr, dc)size算法设计与分析算法设计与分析 /覆盖右上角子棋盘覆盖右上角子棋盘 if (dr = tc +s) /特殊方格在此棋盘中 ChessBoard(tr，tc +s ，dr，dc，s)； else/此棋盘中无特殊方格 /用t号骨牌覆盖左下角 Boardtr+s-1tc+s=t； /覆盖其余方格 Chessboard(tr，tc+s，tr+s-1，tc+s，s)； .void

54、outputBoard( int size) for int i=0 ;isize ;i+) for int j=0 ;jsize ;j+)； coutsetw(5)board ij; cout 递归与分治递归与分治初始序列a 8 4 5 6 2 1 7 3 归并到b 4 8 5 6 1 2 3 7 复制到a 4 8 5 6 1 2 3 7 归并到b 4 5 6 8 1 2 3 7 复制到a 4 5 6 8 1 2 3 7 归并到b 1 2 3 4 5 6 7 8 复制到a 1 2 3 4 5 6 7 8 归并 4，5，6，8 1，2，3，7 从两个序列的头部开始归并：4与1比较，1被移到结果

55、序列；4与2比较，2被移入结果序列4与3比较，3被放入结果序列；4和7比较，4被放入结果序列, 5和7比较.，例如例如二路归并二路归并问题:将n个元素排成非递减顺序。52 temlplate void MergeSort(Type a, int left, int right) if (1eft right) /至少有2个元素 int i = (left + right ) /2; /取中点 MergeSort(a, 1eft, i)； MergeSort(a, i+1, right)； Merge(a, b, 1eft, i, right)；/从a合并到数组b copy(a, b, left

56、, right);/复制回数组a T(n)= d n 递归与分治递归与分治 合并排序合并排序算法如下templatevoid merge(T C, T d ,int l, int m , int r)/把cl:m,cm,r归并到dl,r int: i=l, /第段的游标 j=m+1, /第二段的游标 k=l; /结果的游标 /只要段中存在i和j,则不断进行归并 while (i=m)&(j=r) if cim) for (int q=j; q=r;q+) /前段已完 dk+=cq； else for(int q=i ;q 递归与分治递归与分治 a1:8=8, 4, 1, 7, 11,

57、5, 6, 9, 取元素8作为支点,例如例如分解: aq=8; ap: q-1=4, 1, 7, 5, 6; aq+1:r=11,9; q=6 排序: ap:q-1=1, 4, 5, 6, 7; a q+1:r=9, 11。合并:把ap:q-1中的元素放在支点元素8之前, aq+1:r中的元素放在支点元素之后, 结果1, 4, 5, 6, 7, 8, 9, 1154快速排序算法 template void QuickSort(Type a, int p, int r) if(pr) int q=Partition(a, p, r) QuickSort(a, p, q-1); /对左半段排序 Q

58、uickSort(a, q+1, r); /对右半段排序 templateint Partition(Type a ,int p , int r ) int i=p; j=r+1; type x=ap； /将=x的元素交换到左边区域 /将=x的元素交换到右边区域 while(true) while(a+i x)； if (i=j ) break; swap(ai,aj); ap = aj； a j = x; return j Tmin(n)= O(1) n1 得: Tmin (n)=O(nlogn) 复杂性复杂性分析: 算法设计与分析算法设计与分析 递归与分治递归与分治 快速排序快速排序 Tm

59、ax(n)= O(1) n1 得: Tmax (n)=O(n2) 55Partition:i=1,j=8x=15 1 2 3 4 5 6 7i=2, j=7 15 17 16 14 13 12 11i=3, j=6 15 11 16 14 13 12 17i=6, j=5 15 11 12 14 13 16 17i=6, j=5 15 11 12 13 14 16 17 14 11 12 13 15 16 17while(true) while(a+i x)； if (i=j ) break; swap(ai,aj); ap = aj； a j = x;T=O(n)56随机选择支点的快速排序

60、template void randomizedQuickSort(Type a, int p, int r) if (p 递归与分治递归与分治 快速排序快速排序 template int randomizedPartition(Type a, int p, int r) int i=random( p, r) swap( ai, ap ) return Partition (a,p,r)57算法设计与分析算法设计与分析 递归与分治递归与分治排序算法效率比较排排 序序 方方 法法平平 均均 时时 间间最最 坏坏 情情 况况辅辅 存存选 择 排 序2n2n O (1 )插 入 排 序 . .冒 泡 排 序 . .希 尔 排 序快