1、算法几何和设计算法几何和设计( (研究生研究生) )全册配套课件全册配套课件 算法设计与分析算法设计与分析 Design and Analysis of Design and Analysis of Computer AlgorithmComputer Algorithm3参考教材 王晓东 算法设计与分析（第2版），清华大学出版社，2008 周培德 计算几何算法分析与设计（第2版） 清华大学出版社，2005第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界
2、法第七章第七章 概率算法概率算法第八章第八章 NPNP完全性理论简介完全性理论简介算法设计与分析算法设计与分析 目录目录算算 法法 概概 述述Algorithm IntroductionAlgorithm Introduction第一章第一章介绍算法设计的基本概念介绍算法设计的基本概念及算法分析的方法和准则及算法分析的方法和准则.算法设计与分析算法设计与分析6一系列将问题的输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。 2. 计算机算法与人工算法计算机算法与人工算法 算法设计与分析算法设计与分析 算法概述算法概述1.1 算法 AlgorithmAlgorithm1
3、. 算法定义算法定义 有些问题没有计算机算法有些问题没有计算机算法. . 有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同. . 2).确定性 definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义, ,对每种可能的情况对每种可能的情况, ,算法都算法都 要给出确定的操作要给出确定的操作. . 1).有穷性 finiteness 算法必须在执行有穷步后终止算法必须在执行有穷步后终止, ,且每一步均在有限时间内完成且每一步均在有限时间内完成 3).能行性effectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的, ,算法执
4、行结果要达到预期目的算法执行结果要达到预期目的 3.3.计算机算法的一般特征计算机算法的一般特征 4).有有0 0个或多个输入项个或多个输入项, ,至少有一个输出项至少有一个输出项. .7算法设计与分析算法设计与分析 算法概述算法概述数值型算法数值型算法: :算法中的基本运算为算术运算算法中的基本运算为算术运算. .非数值型算法非数值型算法: :算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算. .串行算法串行算法: :串行计算机上执行的算法串行计算机上执行的算法. .并行算法并行算法: :并行计算机上执行的算法并行计算机上执行的算法. .从处理方式上从处理方式上6. 算法分类算法分类从解
5、法上从解法上5.算法描述语言 1).数据数据: 运算序列中作为运算对象和结果的数据运算序列中作为运算对象和结果的数据. . 2).运算运算: 运算序列中的各种运算运算序列中的各种运算: :赋值赋值, ,算术和逻辑运算算术和逻辑运算 3).控制和转移控制和转移: 运算序列中的运算序列中的控制和转移控制和转移. . 4. .算法的三个要素自然语言自然语言, ,数学语言数学语言, ,流程图流程图, ,程序设计语言等等程序设计语言等等. .8算法设计与分析算法设计与分析 算法概述算法概述7.问题的求解过程2)建立数学模型(UML)1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法
6、分析用科学规范的语言用科学规范的语言, ,对所求解的问题做准确的描述对所求解的问题做准确的描述. .通过对问题的分析通过对问题的分析, ,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述. .根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法. .证明算法对一切合法输入均能在有限次计算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出. .对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算. .将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.
7、 .9算法设计与分析算法设计与分析 算法概述算法概述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, ,
9、则则 e ei i= = e ei i(N,I(N,I ) T=T(N,I)= T=T(N,I)= 10算法设计与分析算法设计与分析 算法概述算法概述 算法的复杂性最好情况最好情况: :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
10、)(, ,NDIm axm axkiiiINet1)(* *, ,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个整数的数组个整数的数组A1.m,m=2A1.m,m=2K K,K,K为正整数为正整数. .对于给定的整数对于给定的整数c, c,要求找到一个下标要求找到一个下标i, i,使得使得Ai=c.Ai=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)(logm+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:=
12、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) )作为算法复杂作为算法复杂性的度量性的度量, ,从而简化分析从而简化分析. .设设T(T(n n) )为算法为算法A A的时间复杂性函数的时间复杂性函数, ,则它是则它是n n的单增函数的单增函数, ,如果存在一如果存在一个函数个函数 使得当使得当n n ,
13、 ,有有 (T(T(n n)- ) / T()- ) / T(n n) )0 0称称 是是T(T(n n) )当当 n n 时的时的渐进性态或或 渐进复杂性. .13算算法设计与分析分析 算法概述算法概述 算法的复杂性2 复杂性的渐进性态 1).渐进性态)(T n )(nT T )(nT T )(nT T )(nT T )(nT T )(T n )(T n 例如例如 T(n)=3n2+4nlogn+7, 则则 可以是3n2. 若进一步假定算法中所有不同元运算的单位执行时间相同若进一步假定算法中所有不同元运算的单位执行时间相同, ,则可不考则可不考虑虑 所包含的系数或常数因子。所包含的系数或常数
14、因子。渐进分析适用于渐进分析适用于n n充分大的情况充分大的情况, ,当问题的规模很小时当问题的规模很小时, ,或比较的两或比较的两算法同阶时算法同阶时, ,则不能做这种简化则不能做这种简化. .14算算法设计与分析分析 算法概述算法概述 算法的复杂性2).2).渐进性态的阶又如算法又如算法1-11-1中中Tmin (m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,Tmin (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
15、 c和自然数和自然数NN0 0 使得当使得当 N N NN0 0 时时, ,有有f( f(NN) ) cg cg ( (NN) ) 则称函数则称函数 f( f(NN ) )在在NN充分大时有充分大时有上界上界, , 且且 g g( (NN) )是它的一个上界是它的一个上界, , 记为记为 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表示法表示法 (算法
16、运行时间的上限 )15算算法设计与分析分析 算法概述算法概述 算法的复杂性例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性T(n)T(n)的阶的阶. .分析:内循环体只需O(1)时间,故for i:= 1 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
17、(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)=O(f) 5. f=O(f) 5. f=O(f) 6. O(cf(n)=O(f(n) 6. O(cf(n)=O(f(n)运算法则内循环共需 16算算法设计与分析分析 算法概述算法概述 算法的复杂性(2)大表示法 (算法运行时间的下限） f(N) =f(N) = ( (g g(N)(N) ) ) 当且仅当当且仅当 f(N) =O(f(N) =O(g
18、g (N)(N) ) ) 且且f(N)=f(N)= ( (g g (N)(N) ) ) 称函称函数数f(N)f(N)与与g g (N)(N)同阶同阶. .算法的渐进复杂性的阶对于算法的效率有着决定性的意义算法的渐进复杂性的阶对于算法的效率有着决定性的意义: :多项式阶算法多项式阶算法( (有效算法有效算法):):时间复杂性与规模时间复杂性与规模N N 的幂同阶的幂同阶. .指数阶算法指数阶算法: :时间复杂性与规模时间复杂性与规模N N 的一个指数函数同阶的一个指数函数同阶. .最优算法最优算法: :时间复杂性达到其下界的算法时间复杂性达到其下界的算法. .如果如果 正常数正常数c c和自然数
19、和自然数NN0 0使得当使得当 N N NN0 0 时时, , 有有f(N)f(N) c cg g (N) (N) 则则称函数称函数f(N)f(N)在在NN充分大时有充分大时有下限下限, , 且且 g g(N)(N)是它的一个下限是它的一个下限, ,记为记为f(N) = f(N) = ( (g g (N) ) (N) ) 也称也称f(N)f(N)的的阶阶不低于不低于g g(N)(N)的的阶阶。(3)表示法17算算法设计与分析分析 算法概述算法概述 算法的复杂性图1 时间函数的增长率常见的多项式阶有常见的多项式阶有:O(1)O(1) O(logn)O(logn) O(n)O(n) O(nlogn
20、)O(nlogn) O(nO(n2 2) O(nO(n3 3) )O(2O(2n n) O(n!)O(n!) 算法概述算法概述 算法的复杂性 3.渐进分析 时间复杂性渐进阶分析的规则:(最坏情况) 1). 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需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
21、). 执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数循环次数. 7). 用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句 对非递归调用,根据调用层次由里向外用规则1-7进行分析； 对递归调用,可建立关于T(n)的的递归方程,求解该方程得到T(n). 例例 题题1-1算法设计与分析算法设计与分析 算法1-2:二分查找 (假定c是A的最后一元)例例 题题 1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t, 加法s
22、, 除法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 and 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算法设计与分析算法设计与分析
23、 已知不重复且从小到大排列的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-search(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) m1m1
24、T(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= 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例例
25、 题题 1-2ni022算算法设计与分析分析 算法概述算法概述 算法的复杂性4).套用公式法 若递归方程形如:T(n)=aT(n/b)+ f(n),可根据f(n)的不同情况套用公式 1)若0,使得 f(n)=O(n logb b a-),则T(n)=(n logb 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
26、=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;直接或间接地调用自身的算法称为递归算法直接或间接地调用自身的算法称为递归算法. .24算算法设计与分析分析 递归与分治递归与分治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
27、); PushStack(p); Factorial *CurOb; Popup(&CurOb); while( Stack is not empty) Popup(&p); p.f=p.n* CurOb.f; delete CurOb; CurOb=p; return CurOb.f;递归程序的栈实现递归程序的栈实现25算算法设计与分析分析 递归与分治递归与分治Fibonacci 数列: F(n)=F(n-1)+F(n-2), F(0)=F(1)=1递归代表一种计算规则递归代表一种计算规则, 有时有函数表示结果有时有函数表示结果,有时没有有时没有.1125125151)(nnnF整数划分问题
28、整数划分问题 n=n1+n2+nk, 划分数划分数p(n)计算的递归方法计算的递归方法有函数表有函数表示示无函数表无函数表示示26算算法设计与分析分析 递归与分治递归与分治例例5 5 整数划分问题整数划分问题将正整数将正整数n n表示成一系列正整数之和：表示成一系列正整数之和：n=n1+n2+n=n1+n2+nk+nk，其中其中n1n2n1n2nk1nk1，k1k1。正整数正整数n n的这种表示称为正整数的这种表示称为正整数n n的划分。求正整数的划分。求正整数n n的不的不同划分个数。同划分个数。 例如正整数例如正整数6 6有如下有如下1111种不同的划分：种不同的划分： 6 6； 5+15
29、+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+1。27算算法设计与分析分析 递归与分治递归与分治(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。(3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。例5 整数划分问题在本例中，如果设p(n)为正整数n的划分数
30、，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。28算算法设计与分析分析 递归与分治递归与分治11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n
31、,n)。 m=n的划分只有一个最大加数达是m的划分个数等于将m从n中减去后n-m中最大加数是m的划分个数29例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。30算算法设计与分析分析 递归与分治递归与分治递归代表一种计算规
32、则递归代表一种计算规则, 有时其计算出的实现过程很难人工模拟有时其计算出的实现过程很难人工模拟.用已知方法将上用已知方法将上n-1盘盘, 从从a移到移到ccabvoid Hanoi (int n, int a, int b, int c) if(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优点：优点：结构清晰，可读性强，而且容易用数学归纳法结构清晰，可读性强，而且容
33、易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费的计算时间还是占用的存储空间都比非递归算法要多。非递归算法要多。算算法设计与分析分析 递归与分治递归与分治解决方法：解决方法：在递归算法中消除递归调用，使其转在递归算法中消除递归调用，使其转化为非递归算法。化为非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归用工
34、作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化，只不过人工做了本来由编译器做的事情，优化效果不明显。效果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过、通过变换能变换能将一些递归转化为非递归，从而将一些递归转化为非递归，从而迭代求出结果。迭代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。算算法设计与分析分析 递归与分治递归与分治33算算法设计与分析分析 递归与分治递归与分治2.2 分治(Divide and Conquer)基本思想 Divide-and-
35、Conquer(P) if ( |P|=n0) Adhoc(P); 直接求解问题 P divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i 递归与分治递归与分治设问题P(n)分解成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
36、(P); divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i = k; i+) yi=Divide-and-Conquer(Pi); return Merge( yl ,., yk); f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换, 棋盘覆盖,排序,选择 等.O(1)35)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*
37、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(nogl212n2nn/2*2*2nT(n)221nogl01nogl01nogl0222nOnnnnjjjjj当当k=m=2,f(n)=2n k=m=2,f(n)=2n 时时, ,验证此公式验证此公式: :算法设计与分析算法设计与分析 已知不重复且从小到大排列的已知不重复且从小到大排列的mm个整数的数组个整数的数组A1.m,m=2A1.m,m=2K
38、K,K,K为正整数为正整数. .对于给定的整数对于给定的整数c, c,要求找到一个下标要求找到一个下标i, i,使得使得Ai=c.Ai=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;
39、/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; w h i l e n o t
40、f o u n d a n d U = L d o 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 e l s e U : = i - 1 2(logn+1) if found then b-search:=1 else b-search:=0 n=2hh=logn39算法设计与分析算法设计与分析 递归与分治递归与分治2.4 大整数的乘法 设计一个有效的算法，可以进行两个设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算u小学的
41、方法：O(n2) 效率太低u分治法: X = 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 ()(nnnOnTOnT40算法设计与分析算法设计与分析 递归与分治递归与分治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
42、)-ac-bd) 2n/2 + bd细节问题细节问题：两个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)的产生。该方法也可以
43、看作是一个复杂的分治算法。算法设计与分析算法设计与分析 递归与分治递归与分治 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
44、) X,Y为2个小于2n的二进制整数，返回结果为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重写为：222112112221121
45、122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC复杂度分析复杂度分析T(n)=O(n3)22)()2/(8) 1 ()(2nnnOnTOnT为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2
46、112MMC4321MMC731522MMMMC复杂度分析复杂度分析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算法设计与
47、分析算法设计与分析procedure STRASSEN(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+A
48、21，B11+B12，M7)731543216245MMMMMMMMMMMMC:=矩阵相乘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之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上
49、界是 O(n2.376)是否能找到O(n2)的算法？48问题陈述:在一个2k2k个方格组成的棋盘中,恰有一方格残缺 残缺方格的位置有22k种。故对任何k0,残缺棋盘有22k种. 要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型骨牌不得重叠覆盖。2k 2k 的棋盘覆盖中，用到的骨牌数为(4k-1)/32.6 棋盘覆盖算法设计与分析算法设计与分析 递归与分治递归与分治49分治算法: 当k0时,将2k 2k棋盘分割为4个2k-1 2k-1子棋盘 残缺方格必位于4个子棋盘之一其余3个子棋盘中无残缺方格为此将剩余3棋盘转化为残缺棋盘. 用一个L型骨牌覆盖这3个较小棋盘的结合处.这3个子棋盘上被L型骨
50、牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为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)与所需骨牌数同阶算法设计与分析算法设计与分析 递归与分治递归与分治算法设计与分析算法设计与分析 void ChessBoard(int tr, int tc, int dr, int dc
