1、计算机计算机算法分析与设计算法分析与设计(研究生研究生)全册配套课件全册配套课件(一一) 计算机算法设计与计算机算法设计与分析分析 算法设计与分析算法设计与分析 目录目录第一章第一章 算法及计算几何概述算法及计算几何概述第三章第三章 凸壳及其算法凸壳及其算法第八章第八章 动态规划动态规划第九章第九章 贪心算法贪心算法第十章第十章 回朔法回朔法第十一章第十一章 分支限界法分支限界法第七章第七章 递归与分治递归与分治第六章第六章 NPNP完全性理论简介完全性理论简介第二章第二章 多边形与几何体定位多边形与几何体定位第四章第四章 VoronoiVoronoi图及其应用图及其应用第五章第五章 交与并交
2、与并4参考教材 王晓东 算法设计与分析，清华大学出版社，2003 周培德 计算几何算法分析与设计 清华大学出版社，2000算算 法法 概概 述述Algorithm IntroductionAlgorithm Introduction第一章第一章介绍算法设计的基本概念介绍算法设计的基本概念及算法分析的方法和准则及算法分析的方法和准则.算法设计与分析算法设计与分析6一系列将问题的输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。 算法设计与分析算法设计与分析 算法概述算法概述1.1 算法 AlgorithmAlgorithm 2).确定性 definiteness 算法的
3、每个步骤必须有明确的意义算法的每个步骤必须有明确的意义, ,对每种可能的情况对每种可能的情况, ,算法都算法都 要给出确定的操作要给出确定的操作. . 1).有穷性 finiteness 算法必须在执行有穷步后终止算法必须在执行有穷步后终止, ,且每一步均在有限时间内完成且每一步均在有限时间内完成 3).能行性effectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的, ,算法执行结果要达到预期目的算法执行结果要达到预期目的 3.3.计算机算法的一般特征计算机算法的一般特征 4).有有0 0个或多个输入项个或多个输入项, ,至少有一个输出项至少有一个输出项. .1 1
4、 问题问题问题是一组需要完成的任务，数学上可将问题看作函数问题是一组需要完成的任务，数学上可将问题看作函数2 2 算法算法7算法设计与分析算法设计与分析 算法概述算法概述数值型算法数值型算法: :算法中的基本运算为算术运算算法中的基本运算为算术运算. .非数值型算法非数值型算法: :算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算. .串行算法串行算法: :串行计算机上执行的算法串行计算机上执行的算法. .并行算法并行算法: :并行计算机上执行的算法并行计算机上执行的算法. .从处理方式上从处理方式上6. 算法分类算法分类从解法上从解法上5.算法描述语言 1).数据数据: 运算序列中作为运
5、算对象和结果的数据运算序列中作为运算对象和结果的数据. . 2).运算运算: 运算序列中的各种运算运算序列中的各种运算: :赋值赋值, ,算术和逻辑运算算术和逻辑运算 3).控制和转移控制和转移: 运算序列中的运算序列中的控制和转移控制和转移. . 4. .算法的三个要素自然语言自然语言, ,数学语言数学语言, ,流程图流程图, ,程序设计语言等等程序设计语言等等. .8算法设计与分析算法设计与分析 算法概述算法概述7.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言用科学规范的语言, ,对所求解的问题做准确的描述对所求
6、解的问题做准确的描述. .通过对问题的分析通过对问题的分析, ,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述. .根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法. .证明算法对一切合法输入均能在有限次计算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出. .对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算. .将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序. .9算法设计与分析算法设计与分析 算法概述算法概述1.2 1.2 算法复
7、杂性分析算法复杂性分析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,I ) T=T(N,I
9、)= 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 mi in nkiiiINet1)(, ,NDImaxmax kiiiINet1)(* *, ,NDI
10、IPI)T(N,)()(* *, ,INTnDIIP )(NDIminminNDIm ma ax xI 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的概率的概率算法设计与分析算法设计与分析 已知不重复且从小到大排列的已知不重复且从小到大排列的mm个整数的数组个整数的数组A1.m,m=2A1.m,m=2K K,
11、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:=i-1 if found then b-search:=i else b
12、-search:=0 a 13算算法设计与分析分析 算法概述算法概述 算法的复杂性2 复杂性的渐进性态 1).渐进性态)(T n )(nT T )(nT T )(nT T )(nT T )(nT T )(T n )(T n 设设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 时的时的渐进性态或或 渐进复杂性. .在数学上在数学上, ,T(T(n
13、n) )与与 有相同的最高阶项有相同的最高阶项. .可取可取 为略去为略去T(T(n n) )的的低低阶项后剩余的主项阶项后剩余的主项. .当当n n充分大时我们用充分大时我们用 代替代替T(T(n n) )作为算法复杂作为算法复杂性的度量性的度量, ,从而简化分析从而简化分析. . 例如例如 T(n)=3n2+4nlogn+7, 则则 可以是3n2. 若进一步假定算法中所有不同元运算的单位执行时间相同若进一步假定算法中所有不同元运算的单位执行时间相同, ,则可不考则可不考虑虑 所包含的系数或常数因子。所包含的系数或常数因子。渐进分析适用于渐进分析适用于n n充分大的情况充分大的情况, ,当问
14、题的规模很小时当问题的规模很小时, ,或比较的两或比较的两算法同阶时算法同阶时, ,则不能做这种简化则不能做这种简化. .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 c和自然数和自然数NN0 0 使得当使得当 N N NN0 0 时时,
15、,有有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表示法表示法 (算法运行时间的上限 )15算算法设计与分析分析 算法概述算法概述 算法的复杂性
16、例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性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(f+g) 2. O(f)+O(g)=O(f+g) 3. O(f)O(g)
17、=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 g (N)(N) ) ) 且且f(N)=f(N)= ( (g g (N)(
18、N) ) ) 称函称函数数f(N)f(N)与与g g (N)(N)同阶同阶. .算法的渐进复杂性的阶对于算法的效率有着决定性的意义算法的渐进复杂性的阶对于算法的效率有着决定性的意义: :多项式阶算法多项式阶算法( (有效算法有效算法):):时间复杂性与规模时间复杂性与规模N N 的幂同阶的幂同阶. .指数阶算法指数阶算法: :时间复杂性与规模时间复杂性与规模N N 的一个指数函数同阶的一个指数函数同阶. .最优算法最优算法: :时间复杂性达到其下界的算法时间复杂性达到其下界的算法. .如果如果 正常数正常数c c和自然数和自然数NN0 0使得当使得当 N N NN0 0 时时, , 有有f(N
19、)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)O(nlogn) O(nO(n2 2) O(nO(n3 3) )O(2O
20、(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). 执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环
21、次数. 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, 除法d, 减法b.最坏情况Tmax(m) = 6a+4t+2s+d+(
22、2a+2s+3t+d) logmfunction b-search(c) L:=1; U:=m; 2 found:=false; 1 while not found and U=L do 3 i:=(L+U)div2; 3 if c=Ai 1then found:=true 1else if cAi 1 then L:=i+1 1 else U:=i-1 if found then b-search:=i else b-search:=0 1 Logm+1算法设计与分析算法设计与分析 已知不重复且从小到大排列的m个整数的数组A1.m,m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,
23、使得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) m1m1T(m)=T(m)=解得: T(m) =11logm+13= (logm)算法1-3:二分查找递归算法算法设计与
24、分析算法设计与分析 求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例例 题题 1-2ni022算算法设计与分析分析 算法概述算法概述 算法的复杂性3).套用公式法 若递归方程形如:T
25、(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 目录目录算算 法法 概概 述述Algorithm IntroductionAlgorithm Introduction第一章第一章介绍算法设计的基本概念介绍算法设计的基本概念及算法分析的方法和准则及算法分析的方法和准则.算法设计与分析算法设计与分析26一系列将问题的输入转换为输出的计
26、算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。 2. 计算机算法与人工算法计算机算法与人工算法 算法设计与分析算法设计与分析 算法概述算法概述1.1 算法 AlgorithmAlgorithm1. 算法定义算法定义 有些问题没有计算机算法有些问题没有计算机算法. . 有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同. . 2).确定性 definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义, ,对每种可能的情况对每种可能的情况, ,算法都算法都 要给出确定的操作要给出确定的操作. . 1).有穷性 finiteness 算法必须在执行
27、有穷步后终止算法必须在执行有穷步后终止, ,且每一步均在有限时间内完成且每一步均在有限时间内完成 3).能行性effectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的, ,算法执行结果要达到预期目的算法执行结果要达到预期目的 3.3.计算机算法的一般特征计算机算法的一般特征 4).有有0 0个或多个输入项个或多个输入项, ,至少有一个输出项至少有一个输出项. .27算法设计与分析算法设计与分析 算法概述算法概述数值型算法数值型算法: :算法中的基本运算为算术运算算法中的基本运算为算术运算. .非数值型算法非数值型算法: :算法中的基本运算为逻辑运算算法中的基本运算为
28、逻辑运算. .串行算法串行算法: :串行计算机上执行的算法串行计算机上执行的算法. .并行算法并行算法: :并行计算机上执行的算法并行计算机上执行的算法. .从处理方式上从处理方式上6. 算法分类算法分类从解法上从解法上5.算法描述语言 1).数据数据: 运算序列中作为运算对象和结果的数据运算序列中作为运算对象和结果的数据. . 2).运算运算: 运算序列中的各种运算运算序列中的各种运算: :赋值赋值, ,算术和逻辑运算算术和逻辑运算 3).控制和转移控制和转移: 运算序列中的运算序列中的控制和转移控制和转移. . 4. .算法的三个要素自然语言自然语言, ,数学语言数学语言, ,流程图流程图
29、, ,程序设计语言等等程序设计语言等等. .28算法设计与分析算法设计与分析 算法概述算法概述7.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言用科学规范的语言, ,对所求解的问题做准确的描述对所求解的问题做准确的描述. .通过对问题的分析通过对问题的分析, ,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述. .根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法. .证明算法对一切合法输入均能在有限次计算后产生正确输出证
30、明算法对一切合法输入均能在有限次计算后产生正确输出. .对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算. .将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序. .29算法设计与分析算法设计与分析 算法概述算法概述1.2 1.2 算法复杂性分析算法复杂性分析1.复杂性的计量k1I)(N,etiii显然显然, ,它与问题的规模它与问题的规模, ,算法的输入数据及算法本身有关算法的输入数据及算法本身有关. . 将时间复杂性和空间复杂性分别考虑将时间复杂性和空间复杂性分别考虑, ,并用并用T T和和S S表示表示. .则则 T=T(N,I,A) S=S(N,I
31、,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) 算法的复杂性:算法执行所需的时间和空间的数量算法执行所需的时间和空间的数量. .令令 NN: :问题的规模问题的规模 I I: :输入数据输入数据 A A: :算法本身算法本身 则算法的复杂性则算法的复杂性 C=F (N,I,A)C=F (N,I,A)设一台抽象计算机提供的元运算有设一台抽象计算机提供的元运算有k k种种, ,分别记作分别记作O O1 1 ,O,Ok k 设这些元运算每执行一次所需时间分别为
32、设这些元运算每执行一次所需时间分别为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,I ) T=T(N,I)= T=T(N,I)= 30算法设计与分析算法设计与分析 算法概述算法概述 算法的复杂性最好情况最好情况: :T Tminmin(N) = T(N,I) = (N) = T(N,I) = = = = =最坏情况最坏情况:T:Tmaxmax(N) = T(N,I) =(N) = T(N,I) = = = = = 平均情况平
33、均情况:T:Tavgavg(N) = = (N) = = kiiiINet1)(, ,kiiiINet1)(, , kiiiINet1)( , ,)(INT , ,NDIm mi in nkiiiINet1)(, ,NDImaxmax kiiiINet1)(* *, ,NDIIPI)T(N,)()(* *, ,INTnDIIP )(NDIminminNDIm ma ax xI I 例例 题题1-1其中其中 D DNN: :规模为规模为NN的所有合法输入的集合的所有合法输入的集合 I I* *: D: DNN中达到中达到T Tmax max (N)(N)的一个输入的一个输入 : D: DNN中达
34、到中达到T Tmin min (N)(N)的一个输入的一个输入 P(I): P(I): 出现输入为出现输入为I I的概率的概率算法设计与分析算法设计与分析 已知不重复且从小到大排列的已知不重复且从小到大排列的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)
35、(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:=i-1 if found then b-search:=i else b-search:=0 a 33算算法设计与分析分析 算法概述算法概述 算法的复杂性2 复杂性的渐进性态 1).渐进性态)(T n )(nT T )(nT T )(nT T )(nT T )(nT T )(T n )(T n 设设T(T(n n) )为算法为算法A A的时间复杂性函数的时间复杂性函数, ,则它是则它是n n的
36、单增函数的单增函数, ,如果存在一如果存在一个函数个函数 使得当使得当n n , ,有有 (T(T(n n)- ) / T()- ) / T(n n) )0 0称称 是是T(T(n n) )当当 n n 时的时的渐进性态或或 渐进复杂性. .在数学上在数学上, ,T(T(n n) )与与 有相同的最高阶项有相同的最高阶项. .可取可取 为略去为略去T(T(n n) )的的低低阶项后剩余的主项阶项后剩余的主项. .当当n n充分大时我们用充分大时我们用 代替代替T(T(n n) )作为算法复杂作为算法复杂性的度量性的度量, ,从而简化分析从而简化分析. . 例如例如 T(n)=3n2+4nlog
37、n+7, 则则 可以是3n2. 若进一步假定算法中所有不同元运算的单位执行时间相同若进一步假定算法中所有不同元运算的单位执行时间相同, ,则可不考则可不考虑虑 所包含的系数或常数因子。所包含的系数或常数因子。渐进分析适用于渐进分析适用于n n充分大的情况充分大的情况, ,当问题的规模很小时当问题的规模很小时, ,或比较的两或比较的两算法同阶时算法同阶时, ,则不能做这种简化则不能做这种简化. .34算算法设计与分析分析 算法概述算法概述 算法的复杂性2).2).渐进性态的阶又如算法又如算法1-11-1中中Tmin (m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,
38、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 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) ) 的的
39、阶阶不高于不高于g g ( (NN) ) 的的阶阶. . 设设f(N)f(N)和和 g g (N) (N) 是定义在正整数集上的正函数是定义在正整数集上的正函数, ,(1)大大O O表示法表示法 (算法运行时间的上限 )35算算法设计与分析分析 算法概述算法概述 算法的复杂性例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性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(1i
40、ij外循环共需)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)=O(f) 5. f=O(f) 5. f=O(f) 6. O(cf(n)=O(f(n) 6. O(cf(n)=O(f(n)运算法则内循环共需 36算算
41、法设计与分析分析 算法概述算法概述 算法的复杂性(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)同阶同阶. .算法的渐进复杂性的阶对于算法的效率有着决定性的意义算法的渐进复杂性的阶对于算法的效率有着决定性的意义: :多项式阶算法多项式阶算法( (有效算法有效算法):):时间复杂性与规模时间复杂性与规模N N 的幂同阶的幂同阶. .指数阶算法指数阶算法:
42、 :时间复杂性与规模时间复杂性与规模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)是它的一个下限是它的一个下限, ,记为记为f(N) = f(N) = ( (g g (N) ) (N) ) 也称也称f(N)f(N)的的阶阶不低于不低于g g(N)(N)的的阶阶。(
43、3)表示法37算算法设计与分析分析 算法概述算法概述 算法的复杂性图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). 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句
44、 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从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句 对非递归调用,根据调用层次由里向外用规则1-7进行分析； 对递归调用,可建立关于T(n)的的递归方
45、程,求解该方程得到T(n). 例例 题题1-1算法设计与分析算法设计与分析 算法1-2:二分查找 (假定c是A的最后一元)例例 题题 1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t, 加法s, 除法d, 减法b.最坏情况Tmax(m) = 6a+4t+2s+d+(2a+2s+3t+d) logmfunction b-search(c) L:=1; U:=m; 2 found:=false; 1 while not found and U=L do 3 i:=(L+U)div2; 3 if c=Ai 1then found:=true 1else if cAi 1 then L:=i
46、+1 1 else U:=i-1 if found 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-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
47、-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= 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
48、 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-2ni042算算法设计与分析分析 算法概述算法概述 算法的复杂性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 递归与分
49、治递归与分治第二章 递归与分治(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;直接或间接地调用自身的算法称为递归算法直接或间接地调用自身的算法称为递归算法. .44算算法设计与分析分析 递归与分治递归与分治Class Factorial public int n, f; Factorial(m) n=
50、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; CurOb=p; return CurOb.f;递归程序的栈实现递归程序的栈实现45算算法设计与分析分析 递归与分治递归与分治Fibonacci 数列: F(n)=F(n-1)+F(n-2), F
