算法分析与设计(研究生)全册配套课件

算法分析与设计(研究生)全册配套课件

计算机算法设计与分析

算法设计与分析>目录第一章算法及计算几何概述第三章凸壳及其算法第八章动态规划第九章贪心算法第十章回朔法第十一章分支限界法第七章递归与分治第六章NP完全性理论简介第二章多边形与几何体定位第四章Voronoi图及其应用第五章交与并4参考教材王晓东《算法设计与分析》，清华大学出版社，2003周培德《计算几何－算法分析与设计》清华大学出版社，2000算法概述AlgorithmIntroduction第一章介绍算法设计的基本概念及算法分析的方法和准则.算法设计与分析6一系列将问题的输入转换为输出的计算或操作步骤。

算法设计与分析>算法概述1.1算法Algorithm2).确定性

definiteness

算法的每个步骤必须有明确的意义,对每种可能的情况,算法都要给出确定的操作.1).有穷性

finiteness

算法必须在执行有穷步后终止,且每一步均在有限时间内完成3).能行性effectiveness

算法中的每个步骤是能够实现的,算法执行结果要达到预期目的

3.计算机算法的一般特征4).有0个或多个输入项,至少有一个输出项.1问题问题是一组需要完成的任务，数学上可将问题看作函数2算法7算法设计与分析>算法概述数值型算法:算法中的基本运算为算术运算.非数值型算法:算法中的基本运算为逻辑运算.串行算法:串行计算机上执行的算法.并行算法:并行计算机上执行的算法.从处理方式上6.算法分类从解法上5.算法描述语言

1).数据:运算序列中作为运算对象和结果的数据.2).运算:运算序列中的各种运算:赋值,算术和逻辑运算

3).控制和转移:运算序列中的控制和转移.

4.算法的三个要素自然语言,数学语言,流程图,程序设计语言等等.8算法设计与分析>算法概述7.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言,对所求解的问题做准确的描述.通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法.证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序.9算法设计与分析>算法概述1.2算法复杂性分析1.复杂性的计量显然,它与问题的规模,算法的输入数据及算法本身有关.

将时间复杂性和空间复杂性分别考虑,并用T和S表示.则

T=T(N,I,A)S=S(N,I,A)

将A隐含在函数名中,则T=T(N,I,A)简化为T=T(N,I)

算法的复杂性:算法执行所需的时间和空间的数量.令N:问题的规模I:输入数据A:算法本身则算法的复杂性C=F(N,I,A)设一台抽象计算机提供的元运算有k种,分别记作O1,…,Ok

设这些元运算每执行一次所需时间分别为t1,

t2,…,tk

,设算法A中用到Oi的次数为ei,i=1,…,k,则ei=ei(N,I)

T=T(N,I)=

10算法设计与分析>

算法概述>算法的复杂性最好情况:Tmin(N)=T(N,I)=

==最坏情况:Tmax(N)=T(N,I)=

==平均情况:Tavg(N)==例题1-1其中DN:规模为N的所有合法输入的集合

I*:DN中达到Tmax(N)的一个输入

:DN中达到Tmin(N)的一个输入

P(I):出现输入为I的概率算法设计与分析

已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.functionsearch(c) {i:=1; a whileA[i]<candi<mdo 2mt i:=i+1; (m-1)(s+a) ifA[i]=c t thensearch:=i; elsesearch:=0; a }算法1-1:顺序查找例题1-1分析:问题的规模为m,设元运算执行时间为赋值:a,判断:t,加法:s,并设c在A中.最好情况Tmin(m)=2a+3t最坏情况Tmax(m)=(m+1)a+(2m+1)t+(m-1)s平均情况Tavg(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s算法设计与分析

算法1-2:二分查找(假定c是A的最后一元)例题1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m; 2afound:=false; awhilenotfoundandU>=Ldo t(logm+2){i:=(L+U)div2; (a+s+d)(logm+1) ifc=A[i] t(logm+1) thenfound:=true a elseifc>A[i] t(logm+1) thenL:=i+1 (s+a)(logm+1)elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 a}13算法设计与分析>

算法概述>算法的复杂性2

复杂性的渐进性态

1).渐进性态设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数使得当n,有

(T(n)-)/T(n)0称是T(n)当n

时的渐进性态或渐进复杂性.在数学上,T(n)与有相同的最高阶项.可取为略去T(n)的低阶项后剩余的主项.当n充分大时我们用代替T(n)作为算法复杂性的度量,从而简化分析.

例如T(n)=3n2+4nlogn+7,则可以是3n2.

若进一步假定算法中所有不同元运算的单位执行时间相同,则可不考虑所包含的系数或常数因子。渐进分析适用于n充分大的情况,当问题的规模很小时,或比较的两算法同阶时,则不能做这种简化.14算法设计与分析>

算法概述>算法的复杂性2).渐进性态的阶又如算法1-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和自然数N0使得当N

N0时,有f(N)cg(N)

则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,

记为f(N)=O(g(N))

,也称f(N)

的阶不高于g(N)的阶.

设f(N)和g(N)是定义在正整数集上的正函数,(1)大O表示法

(算法运行时间的上限)15算法设计与分析>

算法概述>算法的复杂性例如估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶.分析:内循环体只需O(1)时间,故fori:=1tondoforj:=1toido{s1,s2,s3,s4};s1,s2,s3,s4为单一赋值语句外循环共需

1.O(f)+O(g)=O(max(f,g))2.O(f)+O(g)=O(f+g)3.O(f)·O(g)=O(f·g)4.如果g(n)=O(f(n)),则O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n))=O(f(n))运算法则内循环共需

16算法设计与分析>

算法概述>算法的复杂性(2)大

表示法(算法运行时间的下限）

f(N)=(g(N)

)当且仅当f(N)=O(g(N)

)且f(N)=(g(N)

)称函数f(N)与g(N)同阶.算法的渐进复杂性的阶对于算法的效率有着决定性的意义:多项式阶算法(有效算法):时间复杂性与规模N的幂同阶.指数阶算法:时间复杂性与规模N的一个指数函数同阶.最优算法:时间复杂性达到其下界的算法.如果正常数c和自然数N0使得当N

N0时,有f(N)cg(N)则称函数f(N)在N充分大时有下限,且g(N)是它的一个下限,记为f(N)=(g(N))也称f(N)的阶不低于g(N)的阶。(3)

表示法17算法设计与分析>

算法概述>算法的复杂性图1

时间函数的增长率常见的多项式阶有:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)O(2n)<O(n!)<O(nn)常见的指数阶有:对规模较小的问题,决定算法工作效率的可能是算法的简单性而不是算法执行的时间.当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣.18算法设计与分析>

算法概述>算法的复杂性3.渐进分析

时间复杂性渐进阶分析的规则:(最坏情况)

1).赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间2).执行条件语句if

c

thenS1elseS2的时间为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

suntilc)语句时间=(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+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m; 2found:=false; 1whilenotfoundandU>=Ldo 3{i:=(L+U)div2; 3 ifc=A[i] 1 thenfound:=true 1 elseifc>A[i] 1 thenL:=i+1 1elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 1}Logm+1算法设计与分析已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.例题1-1functionb-search(c,L,U){ifU<Lthen 1b-search:=0 1 else{index:=(L+U)div2; 3element:=A[index]; 2 ifelement=cthen 1 b-search:=index; elseifelement>cthen 1 b-search:=b-search(c,L,index-1);3+T(m/2)elseb-search:=b-search(c,index+1,U);3+T(m/2)};}设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2

m=013m=1

11+T(m/2)m>1T(m)=解得:T(m)=11·logm+13=

(logm)算法1-3:二分查找递归算法算法设计与分析

求Fibonacci数列的前N项a0,a1,…aN

其中,a0=0,a1=1,ai=ai-1+ai-2算法1-4Procedureseq(n)functionA(n){ifn=0then 1 A:=01elseifn=1then 1A:=1 1 elseA:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2)};{ifn<0then1errorelsefori:=0tondo

writeln(A(i)) (1+F(i))};设F(n)是函数A在最坏情况下的时间复杂性,则F(n)满足如下递归方程:设过程seg在最坏情况下的时间复杂性为T(n),则

T(n)=1+(1+F(i))2n=03n=18+F(n-1)+F(n-2)n>1F(n)=例题1-222算法设计与分析

>

算法概述

>算法的复杂性3).套用公式法

若递归方程形如:T(n)=aT(n/b)+f(n),可根据f(n)的不同情况套用公式

1)若

>0,使得f(n)=O(nlogba-

),则T(n)=(n

logba)2)若f(n)=

(nlogba),则T(n)=(nlogba·logn)3)若

>0,使得f(n)=

(nlogba+

),且

c<1,当n充分大时有

af(n/b)

cf(n),则T(n)=(f(n))1).迭代法

将递归方程的的右端项通过迭代展开成级数,然后估计级数和的渐进阶.2).数学归纳法(代入法)

先估计递归方程的显式解,再用数学归纳法证明.

算法设计与分析

DesignandAnalysisofComputerAlgorithm第一章算法概述第二章递归与分治策略第三章动态规划第四章贪心算法第五章回朔法第六章分支限界法第七章概率算法第八章NP完全性理论简介算法设计与分析>目录算法概述AlgorithmIntroduction第一章介绍算法设计的基本概念及算法分析的方法和准则.算法设计与分析26一系列将问题的输入转换为输出的计算或操作步骤。

2.计算机算法与人工算法

算法设计与分析>算法概述1.1算法Algorithm1.算法定义

有些问题没有计算机算法.

有些问题计算机算法与人工算法不同.

2).确定性

definiteness

算法的每个步骤必须有明确的意义,对每种可能的情况,算法都要给出确定的操作.1).有穷性

finiteness

算法必须在执行有穷步后终止,且每一步均在有限时间内完成3).能行性effectiveness

算法中的每个步骤是能够实现的,算法执行结果要达到预期目的

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

1).数据:运算序列中作为运算对象和结果的数据.2).运算:运算序列中的各种运算:赋值,算术和逻辑运算

3).控制和转移:运算序列中的控制和转移.

4.算法的三个要素自然语言,数学语言,流程图,程序设计语言等等.28算法设计与分析>算法概述7.问题的求解过程2)建立数学模型1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言,对所求解的问题做准确的描述.通过对问题的分析,找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法.证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序.29算法设计与分析>算法概述1.2算法复杂性分析1.复杂性的计量显然,它与问题的规模,算法的输入数据及算法本身有关.

将时间复杂性和空间复杂性分别考虑,并用T和S表示.则

T=T(N,I,A)S=S(N,I,A)

将A隐含在函数名中,则T=T(N,I,A)简化为T=T(N,I)

算法的复杂性:算法执行所需的时间和空间的数量.令N:问题的规模I:输入数据A:算法本身则算法的复杂性C=F(N,I,A)设一台抽象计算机提供的元运算有k种,分别记作O1,…,Ok

设这些元运算每执行一次所需时间分别为t1,

t2,…,tk

,设算法A中用到Oi的次数为ei,i=1,…,k,则ei=ei(N,I)

T=T(N,I)=

30算法设计与分析>

算法概述>算法的复杂性最好情况:Tmin(N)=T(N,I)=

==最坏情况:Tmax(N)=T(N,I)=

==平均情况:Tavg(N)==例题1-1其中DN:规模为N的所有合法输入的集合

I*:DN中达到Tmax(N)的一个输入

:DN中达到Tmin(N)的一个输入

P(I):出现输入为I的概率算法设计与分析

已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.functionsearch(c) {i:=1; a whileA[i]<candi<mdo 2mt i:=i+1; (m-1)(s+a) ifA[i]=c t thensearch:=i; elsesearch:=0; a }算法1-1:顺序查找例题1-1分析:问题的规模为m,设元运算执行时间为赋值:a,判断:t,加法:s,并设c在A中.最好情况Tmin(m)=2a+3t最坏情况Tmax(m)=(m+1)a+(2m+1)t+(m-1)s平均情况Tavg(m)=0.5(m+3)a+(m+2)t+0.5(m-1)s算法设计与分析

算法1-2:二分查找(假定c是A的最后一元)例题1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(m)=6a+4t+2s+d+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m; 2afound:=false; awhilenotfoundandU>=Ldo t(logm+2){i:=(L+U)div2; (a+s+d)(logm+1) ifc=A[i] t(logm+1) thenfound:=true a elseifc>A[i] t(logm+1) thenL:=i+1 (s+a)(logm+1)elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 a}33算法设计与分析>

算法概述>算法的复杂性2

复杂性的渐进性态

1).渐进性态设T(n)为算法A的时间复杂性函数,则它是n的单增函数,如果存在一个函数使得当n,有

(T(n)-)/T(n)0称是T(n)当n

时的渐进性态或渐进复杂性.在数学上,T(n)与有相同的最高阶项.可取为略去T(n)的低阶项后剩余的主项.当n充分大时我们用代替T(n)作为算法复杂性的度量,从而简化分析.

例如T(n)=3n2+4nlogn+7,则可以是3n2.

若进一步假定算法中所有不同元运算的单位执行时间相同,则可不考虑所包含的系数或常数因子。渐进分析适用于n充分大的情况,当问题的规模很小时,或比较的两算法同阶时,则不能做这种简化.34算法设计与分析>

算法概述>算法的复杂性2).渐进性态的阶又如算法1-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和自然数N0使得当N

N0时,有f(N)cg(N)

则称函数f(N)在N充分大时有上界,且g(N)是它的一个上界,

记为f(N)=O(g(N))

,也称f(N)

的阶不高于g(N)的阶.

设f(N)和g(N)是定义在正整数集上的正函数,(1)大O表示法

(算法运行时间的上限)35算法设计与分析>

算法概述>算法的复杂性例如估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶.分析:内循环体只需O(1)时间,故fori:=1tondoforj:=1toido{s1,s2,s3,s4};s1,s2,s3,s4为单一赋值语句外循环共需

1.O(f)+O(g)=O(max(f,g))2.O(f)+O(g)=O(f+g)3.O(f)·O(g)=O(f·g)4.如果g(n)=O(f(n)),则O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n))=O(f(n))运算法则内循环共需

36算法设计与分析>

算法概述>算法的复杂性(2)大

表示法(算法运行时间的下限）

f(N)=(g(N)

)当且仅当f(N)=O(g(N)

)且f(N)=(g(N)

)称函数f(N)与g(N)同阶.算法的渐进复杂性的阶对于算法的效率有着决定性的意义:多项式阶算法(有效算法):时间复杂性与规模N的幂同阶.指数阶算法:时间复杂性与规模N的一个指数函数同阶.最优算法:时间复杂性达到其下界的算法.如果正常数c和自然数N0使得当N

N0时,有f(N)cg(N)则称函数f(N)在N充分大时有下限,且g(N)是它的一个下限,记为f(N)=(g(N))也称f(N)的阶不低于g(N)的阶。(3)

表示法37算法设计与分析>

算法概述>算法的复杂性图1

时间函数的增长率常见的多项式阶有:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)O(2n)<O(n!)<O(nn)常见的指数阶有:对规模较小的问题,决定算法工作效率的可能是算法的简单性而不是算法执行的时间.当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣.38算法设计与分析>

算法概述>算法的复杂性3.渐进分析

时间复杂性渐进阶分析的规则:(最坏情况)

1).赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间2).执行条件语句if

c

thenS1elseS2的时间为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

suntilc)语句时间=(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+(2a+2s+3t+d)logmfunctionb-search(c){L:=1;U:=m; 2found:=false; 1whilenotfoundandU>=Ldo 3{i:=(L+U)div2; 3 ifc=A[i] 1 thenfound:=true 1 elseifc>A[i] 1 thenL:=i+1 1elseU:=i-1 }iffoundthenb-search:=i elseb-search:=0 1}Logm+1算法设计与分析已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.例题1-1functionb-search(c,L,U){ifU<Lthen 1b-search:=0 1 else{index:=(L+U)div2; 3element:=A[index]; 2 ifelement=cthen 1 b-search:=index; elseifelement>cthen 1 b-search:=b-search(c,L,index-1);3+T(m/2)elseb-search:=b-search(c,index+1,U);3+T(m/2)};}设T(m)是b-search在最坏情况下的时间复杂性,则T(m)满足如下递归方程:2

m=013m=1

11+T(m/2)m>1T(m)=解得:T(m)=11·logm+13=

(logm)算法1-3:二分查找递归算法算法设计与分析

求Fibonacci数列的前N项a0,a1,…aN

其中,a0=0,a1=1,ai=ai-1+ai-2算法1-4Procedureseq(n)functionA(n){ifn=0then 1 A:=01elseifn=1then 1A:=1 1 elseA:=A(n-1)+A(n-2) 6+F(n-1)+F(n-2)};{ifn<0then1errorelsefori:=0tondo

writeln(A(i)) (1+F(i))};设F(n)是函数A在最坏情况下的时间复杂性,则F(n)满足如下递归方程:设过程seg在最坏情况下的时间复杂性为T(n),则

T(n)=1+(1+F(i))2n=03n=18+F(n-1)+F(n-2)n>1F(n)=例题1-242算法设计与分析

>

算法概述

>算法的复杂性4).套用公式法

若递归方程形如:T(n)=aT(n/b)+f(n),可根据f(n)的不同情况套用公式

1)若

>0,使得f(n)=O(nlogba-

),则T(n)=(n

logba)2)若f(n)=

(nlogba),则T(n)=(nlogba·logn)3)若

>0,使得f(n)=

(nlogba+

),且

c<1,当n充分大时有

af(n/b)

cf(n),则T(n)=(f(n))设a0,a1,…an,..是任意数列,称f(x)=a0+a1x+…+anxn+…为数列的母函数若取数列为算法的时间复杂性函数{T(n)},则其母函数为:

f(x)=T(0)+T(1)x+…+

T(n)xn…若能由T(n)的递归方程求出T(n)的母函数,其展开式第n项系数即为T(n).4递归方程解的渐进阶1).母函数法2).迭代法

将递归方程的的右端项通过迭代展开成级数,然后估计级数和的渐进阶.3).数学归纳法(代入法)

先估计递归方程的显式解,再用数学归纳法证明.43算法设计与分析>

递归与分治第二章递归与分治(DivideandConquer)2.1递归的概念例1.阶乘函数f(n)=n!=n*(n-1)*(n-2)*…3*2*1 =n*[(n-1)!]=n*f(n-1)intfactorial(intn){ intf; if(n==0)f=1; elsef=n*factorial(n-1);//调用自身函数

returnf;}直接或间接地调用自身的算法称为递归算法.44算法设计与分析>

递归与分治ClassFactorial{publicintn,f;Factorial(m){n=m;f=1;} };intfactorial(intn){Factorial*p;for(inti=n;i>0;i--){p=newFactorial(i);PushStack(p);}

Factorial*CurOb;Popup(&CurOb);while(Stackisnotempty){Popup(&p);p.f=p.n*CurOb.f;deleteCurOb;CurOb=p;}returnCurOb.f;}递归程序的栈实现45算法设计与分析>

递归与分治Fibonacci数列:F(n)=F(n-1)+F(n-2),F(0)=F(1)=1递归代表一种计算规则,有时有函数表示结果,有时没有.整数划分问题n=n1+n2+…+nk,划分数p(n)计算的递归方法q(n,m)是所有划分中最大加数不大于m的划分数有函数表示无函数表示m=n的划分只有一个最大加数达是m的划分个数等于将m从n中减去后n-m中最大加数是m的划分个数46算法设计与分析>

递归与分治递归代表一种计算规则,有时其计算出的实现过程很难人工模拟.用已知方法将上n-1盘,从a移到ccab将n盘子从a移到b:1.每次只移一个2.大盘不能压小盘3.架子c作为辅助架voidHanoi(intn,inta,intb,intc){if(n>0){Hanoi(n-1,a,c,b);move(a,b);Hanoi(n-1,c,b,a);}}设对于任意n,方法已知(实际未知)将第n盘,从a移到b用已知方法将上n-1盘,从c移到b47算法设计与分析>

递归与分治2.2分治(DivideandConquer)基本思想Divide-and-Conquer(P)if(|P|<=n0)Adhoc(P);直接求解问题PdividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);将p1,p2,…pk的解y1,y2,…yk合并成p的解问题的规模阈值算法一般模式将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止.在分治法中,子问题的解法通常与原问题相同,自然导致递归过程.应用当中,通常将问题分解为k个(k=2)大小相等的子问题.例题1-148算法设计与分析>

递归与分治设问题P(n)分解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则分治法解规模为n的问题的最坏时间复杂性函数T(n)满足:

T(n)=算法的时间复杂性Divide-and-Conquer(P)if(|P|<=n0)Adhoc(P);dividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(yl,...,yk);f(n)kT(n/m)T(1)=O(1)T(n)=kT(n/m)+f(n)解得:适用问题大数相乘,矩阵乘法,快速富立叶变换,棋盘覆盖,排序,选择等.O(1)49T(1)=1T(n)=2T(n/2)+2nT(n)=2[2T(n/22)+2*n/2]+2n=22T(n/22)+2*2n=22[2T(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)当k=m=2,f(n)=2n时,验证此公式:算法设计与分析

已知不重复且从小到大排列的m个整数的数组A[1...m],m=2K,K为正整数.对于给定的整数c,要求找到一个下标i,使得A[i]=c.找不到返回0.functionsearch(c) {i:=1; 1 whileA[i]<candi<mdo i:=i+1; (3+2)m ifA[i]=c thensearch:=i; elsesearch:=0; 1+1 }算法1-1:顺序查找例题1-1最好情况Tmin(m)=4,最坏情况Tmax(m)=3+5m,Tmin(m)=O(1)Tmax(m)=O(m)//i:=1,A[1]<c,ifA[1]=c,search:=151intbinarySearch(inta[],intx,intleft,intright)//Arraya[]hasbeensorted{intmiddle;middle=(left+right)/2;//3if(x==a[middle])returnmiddle;//1if(x>a[middle])left=middle+1;//3elseright=middle-1;

returnbinarySearch(a,x,left,right); }二分搜索算法:规模缩小为1/2,所以m=2,细化分枝为1,所以k=1.f(n)=7Log21=0T(n)=n0+7log2n=1+7log2n=O(log2n)算法设计与分析

算法1-2:二分查找例题1-1最坏情况Tmax(n)=O(logn)functionb-search(c){L:=1;U:=n; found:=false; whilenotfoundandU>=Ldo 3(logn+1){i:=(L+U)div2; 3(logn+1) ifc=A[i] logn+1 thenfound:=true elseifc>A[i] logn+1 thenL:=i+1 elseU:=i-1 2(logn+1)}iffoundthenb-search:=1 elseb-search:=0 }n=2hh=logn53算法设计与分析>

递归与分治问题:

设X,Y是两个n位二进制数,求XY.分治算法思路:若两个1位数相乘或相加看作1步运算,按传统乘法需O(n2)次运算.将每个n(n=2K)位的二进制整数分为2段,每段的长为n/2位计算XY须3次n/2位整数的乘法,6次加.减和2次移位X=A2n/2+By=C2n/2+D。XY＝(A2n/2+B)(C2n/2+D)＝AC2n+(AD+CB)2n/2+BD

T(n)=T(1)=O(1)T(n)=4T(n/2)+O(n)计算XY须4次n/2位整数的乘法,3次不超过2n位的整数加法,2次移位(乘2n

和乘2n/2).XY的T(n)满足解得T(n)=O(n2)

T(n)=T(1)=O(1)T(n)=3T(n/2)+O(n)解得T(n)=O(nlog3)2.4大整数的乘法没有改善改进:XY＝AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD算法算法设计与分析>

递归与分治{S=SIGN(X)*SIGN(Y)；

X:=ABS(X)；Y:=ABS(Y)；

ifn=lthenif(X=1)and(Y=1)thenreturn(S)elsereturn(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的二进制整数，返回结果为X和Y的乘积XY}functionMULT(X,Y,n)大数相乘的分治递归算法二进制大整数乘法同样可应用于十进制大整数的乘法存放XY的符号存放三个乘积算法552.5矩阵相乘的Strassen法常规算法:设矩阵A=(aij)n

n,B=(bij)n

n,C=A

B=(cij)n

n计算C共需n

n2个乘法,n2(n-1)个加法.分治算法:划分A,B为四个n/2(n=2K)阶方阵,则:C11=A11B11+A12B21C12=A11B11+A12B21C21=A11B11+A12B21C22=A11B11+A12B21若n=2,可直接计算C;若n>2,C需8个n/2阶方阵的乘法和4个加法.

T(n)=T(2)=O(1)T(n)=8T(n/2)+O(n2)

得:T(n)=O(n3)

T(n)=O(n3)改进C11=M5+M4-M2+M6C12=M1+M2C21=M3+M4C22=M5+M1-M3-M7M1=A11(B12-B21)M2=(A11+A12)

B22M3=(A21+A22)

B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12+A22)(B21+B22)M7=(A11-A21)(B11+B12)

验证: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算法设计与分析>

递归与分治算法算法设计与分析procedureSTRASSEN(n,A,B,C)；

{ifn=2thenMATRIX_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)C:=矩阵相乘Strassen算法

T(n)=T(2)=O(1)T(n)=7T(n/2)+18(n/2)2

得:T(n)=O(nlog7)=O(n2.81)分析:

算法//18次小矩阵相加57问题陈述:在一个2k

2k个方格组成的棋盘中,恰有一方格残缺残缺方格的位置有22k种。故对任何k≥0,残缺棋盘有22k种.要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型骨牌不得重叠覆盖。2k

2k

的棋盘覆盖中，用到的骨牌数为(4k-1)/32.6棋盘覆盖算法设计与分析>

递归与分治58分治算法:

当k>0时,将2k

2k棋盘分割为4个2k-1

2k-1子棋盘

残缺方格必位于4个子棋盘之一其余3个子棋盘中无残缺方格为此将剩余3棋盘转化为残缺棋盘.用一个L型骨牌覆盖这3个较小棋盘的结合处.这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的残缺方格,原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为11棋盘.算法分析:设T(k)为覆盖2k

2k残缺棋盘的时间,

当k=0时覆盖它需要常数时间O(1)当k>0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需四次递归调用,共需时间4T(k-1),

T(k)=O(1)4T(k-1)+O(1)

得:T(k)=

(4k)与所需骨牌数同阶算法设计与分析>

递归与分治算法设计与分析

voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return；//tr,tc:Cornerrow&columnno.