算法设计与分析课件

第一章

算法概述第二章 递归与分治策略第三章 动态规划1第四章 贪心算法第五章 回朔法第六章 分支限界法第七章 随机化算法算法设计与分析>目录1.1

算法与程序2算法复杂度分析NP完全性理论算法设计与分析>第一章目录“算法是任何定义好的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。”1.1

算法与程序1

算法定义及其特性算法设计与分析>算法概述算法: 是将问题的输入转化为输出的一系列计算或操作步骤.3算法设计与分析>算法概述算法描述举例例：求两个不全为0的非负整数m,n的最大公约数gcd(m,n)的欧几里德算法描述:如果n=0,返回m的值作为结果，过程结束；否则，进入第二步；用n去除m，将余数赋给r;将n的值赋给m，将r的值赋给n,返回第一步。4计算机算法与人工算法例如 求定积分:

s=人工处理步骤为找出f(x)的源函数F(x)利用牛-莱公式:s=F(b)-F(a)算法设计与分析>算法概述计算机算法：计算定积分采用数值积分的方法,得到一个近似解.有些问题没有计算机算法.有些问题计算机算法与人工算法不同.5算法设计与分析>算法概述算法的定义因看待的角度不同而不同6

哲学家：算法是解决一个问题的抽象行为序列。

码农：算法是一个计算过程，它接受一些输入，并产生某些输出。

高大上：算法是解决一个精确定义的计算问题的工具。核心：算法是解决问题的办法和法则，算法必须能够让人一步一步照着执行。算法的特征算法设计与分析>算法概述1.有穷性一个算法须在执行有限个运算步后终止,每一步必须在有限时间内完成.实际应用中,算法的有穷性应该包括执行时间的合理性.程序是算法的程序设计语言的具体实现.可不满足性质1.一个算法面向一个问题，而不是仅仅求解一个问题的实例操作系统程序：是一个在无限循环中执行的程序，而不是一个算法。7算法设计与分析>算法概述例如 计算分段函数

f(x)

=1

x>1000

x<108算法描述：输入变量x,

若x大于100的数，输出1;

若x小于10的数，输出0.

输入10<=x<=100,则算法在异常情况下,执行结果是不确定的.2.确定性算法的每一步骤必须有确定的含义,对每一种可能出现的情况,算法都应给出确定的操作,不能有多义性.3.能行性算法中的每个步骤是能实现的,

如

x/0; 负数开方…算法的执行结果达到预期目的,正确,有效.输入有0个或多个输入项.输出算法产生至少有一个输出项算法设计与分析>算法概述9问题的陈述理解问题，并用科学规范的语言把所求解问题进行准确的描述,包括所有已知条件和输出要求.建立数学模型通过对问题分析,找出其中所有操作对象以及对象之间的关系,并用数学语言加以描述. 对非数值型解法来说,数学模型通常是链表,树,图,集合等数据结构.2.算法设计过程(程序设计过程)算法设计与分析>算法概述10算法设计根据数据模型, 给出求解问题的一系列步骤,且这些步骤可通过计算机的各种操作来实现.算法的正确性证明算法的正确性:对一切合法的输入,算法均能在有限次的计算后产生正确的输出.算法的程序实现将一个算法描述正确地编写成机器语言程序.算法设计与分析>算法概述116.算法分析对执行该算法所消耗的计算机资源进行估算,对数值型算法还需分析算法的稳定性和误差等问题.计算机资源中最重要的是时间和空间资源,执行一个算法程序需要的时间和占用的内存空间分别称为算法的时间复杂度和空间复杂性.算法设计与分析>算法概述12描述算法的方式一般有三种:自然语言,流程图,伪代码语言。伪代码描述介于自然语言与程序设计语言之间。3.算法的描述算法设计与分析>算法概述134.

算法结构算法设计与分析>算法概述任何算法都可由顺序结构、选择结构、循环结构这三块“积木”通过组合和嵌套表达出来，遵循这种方法的程序设计，即为结构化程序设计。145.

算法分类从解法上数值型算法:算法中的基本运算为算术运算.非数值型算法:算法中的基本运算为逻辑运算.从处理方式上串行算法:串行计算机上执行的算法.并行算法:并行计算机上执行的算法.本课程主要介绍非数值型的串行算法.算法设计与分析>算法概述15算法的复杂性:指执行算法所消耗或占用的资源的数量一个算法所需资源越多,我们就说它的复杂性越高,反之则低.空间复杂性算法的复杂性时间复杂性1.2

算法的复杂性分析算法设计与分析>算法概述16考虑空间复杂性的理由

在多用户系统中运行时，需指明分给该程序的内存大小；

需预先知道计算机系统是否有足够的内存来运行该程序；

一个问题可能有若干个不同的内存解决方案，从中择取；

用空间复杂性估计一个程序可能解决的问题的最大规模。算法设计与分析>算法概述17算法设计与分析>算法概述考虑时间复杂性的理由18

某些计算机用户需要提供程序运行时间的上限（用户可接受的）；

所开发的程序需要提供一个满意的实时反应。算法设计与分析>算法概述算法分析:(渐进算法分析):对执行算法所消耗或占用的资源进行估算,给出算法耗费的限界函数.需解决两个问题:

如何度量复杂性?

如何分析复杂性?19例如 在数组中找分量c,两个矩阵相乘,表中排序,遍历一棵树,n:数组中分量的个数

n:矩阵的维数n:数组中分量的个数

n:树中节点数1.复杂性的计量算法的复杂性: 算法运行所需的时间和空间的数量.它与算法求解问题的规模n,算法的输入数I

及算法本身有关.问题的规模n:指问题的输入数据或初始数据的量.在不同的问题中,n有不同的表现形式：算法设计与分析>算法概述20<算法不同>算法效率与计算机的性能有关，但此因素对所有算法的影响相同。5*5的矩阵相乘与10*10矩阵的矩阵相乘所需时间<问题规模不算法设计与分析>算法概述空间均不相同；同>找c在数组A中的位置,c=A(1),与c=A(100),所需时间显然也不同入数不同>顺序查找还是折半查找速度也是不一样的.<输21令

n:

问题规模

I:

输入数据杂性,则C=f

(

n,

I,

A

)A:

算法本身

C:

算法的复将时间复杂性和空间复杂性分别考虑,并用T和S表示.则有:T=T(n,

I,

A) S=S

(n,

I,

A)将算法A

隐含在函数名中,不同函数名代表不同算法,则简化为T=T(

n,

I

) S=S(

n,

I

)算法设计与分析>算法概述22仅以时间复杂性为例将复杂性函数具体化.设一台抽象计算机提供的元运算有k种,记作

O1,…,Ok;设这些元运算每执行一次所需时间分别为

t1,…,tk;设在算法A中用到Oi的次数为

ei

,i=1,…,k,则ei=

ei

(n,

I)T=T(n,I)=当问题的规模n和算法确定后,T是输入变元i的函数.算法设计与分析>算法概述23说明：我们不可能对规模为n的每一种合法输入I都计算ei次，因为输入可能是无穷集合,我们只能对规模为n的问题的某类具有代表性的合法输入统计相应的ei.算法设计与分析>算法概述24最好情况:Tmin(n)=T(n,I)===平均情况:Tavg(n)

=

=P(I):

出现输入为I的概25率其中

Dn

:规模为n的所有合法输入的集合最坏情况:Tmax(n)=T(n,I)

===Dn中达到Tmin

(n)的一个输入.Dn中达到Tmax(n)的一个输入.算法设计与分析>算法概述算法设计与分析>算法概述当一个问题的输入规模很大时,算法的结构又很复杂时,采用前面介绍的精确分析就显得过于繁琐,为降低算法分析的代价,同时又保证估算的精确度,引入一个简化的计算模型来评估算法的开销.称为渐进分析.渐进分析是对问题的规模充分大的算法开销的估算。T(n)的渐进复杂性(渐进表达式)

:(T(n)-

)/T(n)→0，n

→∞时渐进阶:

O,

Ω

,

θ262.复杂性的渐进性态如果存在一个函数(T(n)

-使得当n→∞,有)/

T(n)→0称 是T(n)当

n→

∞

时的渐进性态

或 渐进复杂性1.渐进性态设T(n)为算法A的时间复杂性函数(输入值固定.如Tmax,Tmin,Tavg),则它是n

的单增函数。算法设计与分析>算法概述27当n充分大时用 代替T(n)作为算法复杂性的度量,以简化分析比较两个算法时，如果他们的阶不同，就可分出效率高低。故此时只需关心 最高限的阶即可。可忽略最高项系数或低阶项。在数学上,T(n)与 有相同的最高阶项.可取略去T(n)的低阶项后剩余的主项.例如

T(n)=3n2+4nlogn+7,

则 可以是3n2算法设计与分析>算法概述为282.渐进性态的阶例如3n=O(n),

n+1024=O(n),

2n2+11n-10=O(n2)n2=O(n3)

?n3=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表示法

(算法运行时间的上限

)算法设计与分析>算法概述√29三点注意:用来作比较的函数g(n)应该尽量接近f(n).例如3n+2=O(n2)松散的界限；3n+2=O(n)较好的界限不要产生错误界限。例如n2+100n+6，当n<3时，n2+100n+6<106n，由此就认为n2+100n+6＝O(n).f(n)=O(g(n))不能写成g(n)=O(f(n))因为两者并不等价。实际上，这里的等号并不是通常相等的含义。算法设计与分析>算法概述30O(f

)+O(g)=O(

max(f,

g

))O(f

)+O(g)=O(f+g)O(f

)·O(g)=O(f·g)如果g(n)=O(f

(n)),则O(f

)+O(g)=O(f

)f=O(

f

)O(

cf

(n))=O(

f(n))算法设计与分析>算法概述运算规则31证明:O(f

)+O(g)=O(max(f,g))算法设计与分析>算法概述设F(N)=O(f).根据O的定义,存在正常数C1和自然数N1,使得对所有N≥N1,有F(N)≤C1f(N).类似G(N)=O(g).根据O的定义,存在正常数C2和自然数N2,使得对所有N≥N2,有G(N)≤C2g(N).令C3=max{C1,C2},N3=max{N1,N2},h(N)=max{f,g},则对所有N≥N3,有F(N)≤C1f(N)

≤C1h(N)≤C3h(N).类似G(N)≤C2g(N)≤C2h(N)≤C3h(N).O(f

)+O(g)=

F(N)

+G(N)≤C3h(N)+C3h(N)=2C3h(N)=

O(h)=O(

max(

f,

g

)

)32例 估计如下二重循环的Tmax(n)的阶.分析:内循环体只需O(1)时间,故for

i:=

1ton

dofor

j:=1toi

do{s1,s2,s3,s

4};

s1,s2,s3,s4为单一赋值语句内循环共需外循环共需算法设计与分析>算法概述2.

O(f)+O(g)=O(f+g)33(2)

大Ω表示法

(算法运行时间的下限）若∃正常数c和自然数N0使得当

n

≥

N0

时,有f(n)≥cg(n)则称函数f(n)在n充分大时有下限,

且

g(n)是它的一个下限,记为f(n)=Ω

(g(n)

)

也称f(n)的阶不低于g(n)的阶算法设计与分析>算法概述例

T(n)=c1n2+c2n

,

则T(n)=Ω

(n2),34f

(n)

=θ(g(n)

)等价于

f(n)=O(g

(n)

)

且

f(n)=Ω(g

(n)

)称函数f(n)与g(n)同阶.(3)θ表示法例T(n)=c1n2+c2n,则T(n)=θ

(n2)算法设计与分析>算法概述35多项式阶算法(有效算法):若算法的最坏情形时间复杂度T(n)=O(nk);指数阶算法:若算法的最坏情形时间复杂度T(n)=Ω(an),a>1.

这类算法可认为计算上不可行的算法.算法设计与分析>算法概述算法复杂性分类:36最优算法:

时间复杂性达到其下界的算法.常见的多项式阶有:O(1)

< O(logn)

<常见的指数阶有:O(n)

<

O(nlogn)< O(n2)

<

O(n3)O(2n)

< O(n!)

<

O(nn)一般当n很大时,在计算机上运行比O(logn)复杂性更高的算法已经很困难了.对规模较小的问题,决定算法工作效率的可能是算法的简单性而不是算法执行的时间.当比较两个算法的效率时,若两个算法是同阶的,必须进一步考察阶的常数因子才能辨别优劣.算法设计与分析>算法概述两点说明:37时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。38算法设计与分析>算法概述1.3

NP完全性理论确定性算法：设A是求解问题的一个算法,如果在算法的整个执行过程中,每一步只有一个确定的选择,并且对于同一输入实例运行算法,所得的结果严格一致.P类问题:对于某个判定问题II，对于规模为n的输入，能够在O(nk)得到yes或no的求解。时间内运行一个确定性算法答案，其中k为某一确定常数仅回答yes或no的问题算法设计与分析>算法概述非确定性算法：设A是求解问题的一个算法,如果算法以如下猜测并验证的方式工作,算法A是非确定算法.(1)猜测阶段:对问题的输入实例产程一个任意字符串y,在算法的每一次执行y的值可能不同,猜测以一种非确定性的形式工作;(2)验证阶段:用一个确定性算法验证:a)检查在猜测阶段产生的串y是否是合适的形式，如果不是，算法停止得到no；b)如果y是合适的形式，再验证它是否是问题的解，如果是算法停止得到yes，否则算法停止得到no。算法设计与分析>算法概述NP类问题:对于某个判定问题II，对于规模为n的输入，能够在O(nk)时间内运行一个非确定性算法求解得到yes或no,其中k为某一确定常数，该判定问题II是一个NP类输入转换IO'输出转换OI'算法A问题。NP完全问题：令II是个判定问题，如果问题II属于NP类问题，并且对NP类问题中的每个问题II’，都有(规约),则称判定问题II是个NP完全问题。问题II'问题II算法设计与分析>算法概述NP完全问题P类问题:能在多项式时间内解决的问题。NP类问题:在多项式