算法设计与分析 全套课件PPT文档格式.ppt
《算法设计与分析 全套课件PPT文档格式.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析 全套课件PPT文档格式.ppt（378页珍藏版）》请在冰点文库上搜索。
,巢湖学院计算机科学与技术系,1.3、算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性T（N），需要的空间资源的量称为空间复杂性S（N）。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F（N,I,A）。
一般把时间复杂性和空间复杂性分开，分别用T和S来表示则有：
T=T（N,I）和S=S（N,I）。
（通常，让A隐含在复杂性函数名当中）,巢湖学院计算机科学与技术系,1.3、算法复杂性分析,最坏情况下的时间复杂性：
最好情况下的时间复杂性：
平均情况下的时间复杂性：
其中DN是规模为N的合法输入的集合；
I*是DN中使T（N,I*）达到Tmax（N）的合法输入；
是中使T（N,）达到Tmin（N）的合法输入；
而P（I）是在算法的应用中出现输入I的概率。
巢湖学院计算机科学与技术系,1.3、算法复杂性分析,算法复杂性在渐近意义下的阶：
渐近意义下的记号：
O、o设f（N）和g（N）是定义在正数集上的正函数。
（1）渐近上界O的定义：
如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时上有界，且g（N）是它的一个上界，记为f（N）=O（g（N）。
即f（N）的阶不高于g（N）的阶。
根据O的定义，容易证明它有如下运算规则：
（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）O（Cf（N）=O（f（N），其中C是一个正的常数；
（6）f=O（f）。
巢湖学院计算机科学与技术系,1.3、算法复杂性分析,
（2）渐近下界的定义：
如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时下有界，且g（N）是它的一个下界，记为f（N）=（g（N）。
即f（N）的阶不低于g（N）的阶。
（3）同阶的定义：
定义f（N）=（g（N）当且仅当f（N）=O（g（N）且f（N）=（g（N），即（g（n）=f（n）|存在正常数c1,c2和正整数n0使得对所有nn0有：
c1g（n）f（n）c2g（n），此时称f（N）与g（N）同阶。
定理1：
（g（n）=O（g（n）（g（n）,巢湖学院计算机科学与技术系,1.3、算法复杂性分析,（4）低阶o的定义：
对于任意给定的0，都存在正整数N0，使得当NN0时有f（N）/Cg（N）,则称函数f（N）当N充分大时的阶比g（N）低，记为f（N）=o（g（N）。
（有的书称之为非紧上界）例如，4NlogN+7=o（3N2+4NlogN+7）。
（5）非紧下界记号（g（n）=f（n）|对于任何正常数c0，存在正数和n00使得对所有nn0有：
0cg（n）f（n）。
注意：
f（n）（g（n）g（n）o（f（n）,巢湖学院计算机科学与技术系,渐近分析记号在等式和不等式中的意义,f（n）=（g（n）的确切意义是：
f（n）（g（n）。
一般情况下，等式和不等式中的渐近记号（g（n）表示（g（n）中的某个函数。
例如：
2n2+3n+1=2n2+（n）表示2n2+3n+1=2n2+f（n），其中f（n）是（n）中某个函数。
等式和不等式中渐近记号O,o,和的意义是类似的。
巢湖学院计算机科学与技术系,渐近分析中函数比较,f（n）=O（g（n）ab;
f（n）=（g（n）ab;
f（n）=（g（n）a=b;
f（n）=o（g（n）ab;
巢湖学院计算机科学与技术系,渐近分析记号的若干性质,
（1）传递性：
f（n）=（g（n），g（n）=（h（n）f（n）=（h（n）；
f（n）=O（g（n），g（n）=O（h（n）f（n）=O（h（n）；
f（n）=o（g（n），g（n）=o（h（n）f（n）=o（h（n）；
（2）反身性：
f（n）=（f（n）；
f（n）=O（f（n）；
f（n）=（f（n）.（3）对称性：
f（n）=（g（n）g（n）=（f（n）.（4）互对称性：
f（n）=O（g（n）g（n）=（f（n）；
f（n）=o（g（n）g（n）=（f（n）；
巢湖学院计算机科学与技术系,（5）算术运算：
O（f（n）+O（g（n）=O（maxf（n）,g（n）；
O（f（n）+O（g（n）=O（f（n）+g（n）；
O（f（n）*O（g（n）=O（f（n）*g（n）；
O（cf（n）=O（f（n）；
g（n）=O（f（n）O（f（n）+O（g（n）=O（f（n）。
渐近分析记号的若干性质,巢湖学院计算机科学与技术系,规则O（f（n）+O（g（n）=O（maxf（n）,g（n）的证明：
对于任意f1（n）O（f（n），存在正常数c1和自然数n1，使得对所有nn1，有f1（n）c1f（n）。
类似地，对于任意g1（n）O（g（n），存在正常数c2和自然数n2，使得对所有nn2，有g1（n）c2g（n）。
令c3=maxc1,c2,n3=maxn1,n2,h（n）=maxf（n）,g（n）。
则对所有的nn3，有f1（n）+g1（n）c1f（n）+c2g（n）c3f（n）+c3g（n）=c3（f（n）+g（n）c32maxf（n）,g（n）=2c3h（n）=O（maxf（n）,g（n）.,渐近分析记号的若干性质,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,
（1）单调函数单调递增：
mnf（m）f（n）;
单调递减：
严格单调递增：
mf（n）.
（2）取整函数x：
不大于x的最大整数；
x：
不小于x的最小整数；
巢湖学院计算机科学与技术系,取整函数的若干性质,x-1xxxx+1；
n/2+n/2=n;
对于n0，a,b是大于0的整数，有：
n/a/b=n/ab;
a/b（a+（b-1）/b;
a/b（a-（b-1）/b;
f（x）=x,g（x）=x为单调递增函数。
巢湖学院计算机科学与技术系,（3）多项式函数p（n）=a0+a1n+a2n2+adnd；
ad0;
p（n）=（nd）;
f（n）=O（nk）f（n）多项式有界；
f（n）=O
（1）f（n）c;
kdp（n）=O（nk）;
kdp（n）=（nk）;
kdp（n）=o（nk）;
kdp（n）=（nk）.,算法渐近复杂性分析中常用函数,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（4）指数函数对于正整数m,n和实数a0:
a0=1;
a1=a;
a-1=1/a;
（am）n=amn;
（am）n=（an）m;
aman=am+n;
a1an为单调递增函数;
a1nb=o（an）,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（5）对数函数logn=log2n;
lgn=log10n;
lnn=logen;
logkn=（logn）k;
loglogn=log（logn）;
fora0,b0,c0,巢湖学院计算机科学与技术系,|x|1forx-1,foranya0,logbn=o（na）,算法渐近复杂性分析中常用函数,（5）对数函数,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（6）阶层函数Stirlingsapproximation,巢湖学院计算机科学与技术系,算法分析中常见的复杂性函数,巢湖学院计算机科学与技术系,小规模数据,巢湖学院计算机科学与技术系,中等规模数据,巢湖学院计算机科学与技术系,
（1）选择语句：
（1.1）if语句：
（1.2）？
语句：
if（expression）statement;
elsestatement;
exp1?
exp2:
exp3y=x9?
100:
200;
等价于：
if（x9）y=100;
elsey=200;
用c+描述算法的常用语句,巢湖学院计算机科学与技术系,switch（expression）case1:
statementsequence;
break;
case2:
default:
（1.3）switch语句：
用c+描述算法的常用语句,巢湖学院计算机科学与技术系,（2.1）for循环：
for（init;
condition;
inc）statement;
（2.2）while循环：
while（condition）statement;
（2.3）do-while循环：
dostatement;
while（condition）;
用c+描述算法的常用语句,
（2）迭代语句,巢湖学院计算机科学与技术系,（3.1）return语句：
returnexpression;
（3.2）goto语句：
gotolabel;
label:
用c+描述算法的常用语句,（3）跳转语句：
巢湖学院计算机科学与技术系,算法分析方法举例,例：
顺序搜索算法,templateintseqSearch（Type*a,intn,Typek）for（inti=0;
in;
i+）if（ai=k）returni;
return-1;
巢湖学院计算机科学与技术系,
（1）Tmax（n）=maxT（I）|size（I）=n=O（n）
（2）Tmin（n）=minT（I）|size（I）=n=O
（1）（3）在平均情况下，假设：
（a）搜索成功的概率为p（0p1）；
（b）在数组的每个位置i（0in）搜索成功的概率相同，均为p/n。
算法分析方法举例,巢湖学院计算机科学与技术系,算法分析的基本法则,
（一）非递归算法：
（1）for/while循环循环体内计算时间*循环次数；
（2）嵌套循环循环体内计算时间*所有循环次数；
（3）顺序语句各语句计算时间相加；
（4）if-else语句if语句计算时间和else语句计算时间的较大者。
巢湖学院计算机科学与技术系,templatevoidinsertion_sort（Type*a,intn）Typekey;
/costtimesfor（inti=1;
i=0/c7n-1,巢湖学院计算机科学与技术系,在最好情况下，ti=1,for1in;
在最坏情况下，tii+1,for1in;
巢湖学院计算机科学与技术系,对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort达到其最坏情形。
因此：
由此可见，Tmax（n）=（n2）,巢湖学院计算机科学与技术系,
（二）递归算法复杂性分析,intfactorial（intn）if（n=0）return1;
returnn*factorial（n-1）;
巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型1,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型2,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型3,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型4,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型5,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型6,巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,这个方法为估计形如：
T（n）=aT（n/b）+f（n）
（1）的递归方程解的渐近阶提供三个可套用的公式。
（1）中的a1和b1是常数，f（n）是一个确定的正函数。
（1）是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。
如果用T（n）表示规模为n的原问题的复杂性，用f（n）表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程
（1）。
巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,设a1和b1是常数,f（n）是定义在非负整数上的一个确定的非负函数。
又设T（n）也是定义在非负整数上的一个非负函数，且满足递归方程
（1）。
方程
（1）中的n/b可以是n/b，也可以是n/b。
那么，在f（n）的三类情况下，我们有T（n）的渐近估计式：
若对于某常数0，有则:
巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,若则,巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,若:
对于某常数0，有且对于某常数c1和所有充分大的正整数n有af（n/b）cf（n）;
则T（n）=（f（n）,巢湖学院计算机科学与技术系,（三）最优算法,问题的计算时间下界为（f（n），则计算时间复杂性为O（f（n）的算法是最优算法。
例如，排序问题的计算时间下界为（nlogn），计算时间复杂性为O（nlogn）的排序算法是最优算法。
堆排序算法是最优算法。
巢湖学院计算机科学与技术系,第一章：
作业布置,书面作业：
P5：
算法分析题1-1、1-3、1-6（1、3、5、7）；
上机练习（多选一）：
P6-7：
算法实现题1-1、1-3；
第2章、递归与分治策略,巢湖学院计算机科学与技术系,将要求解的较大规模的问题分割成k个更小规模的子问题。
算法总体思想,n,T（n/2）,T（n/2）,T（n/2）,T（n/2）,T（n）,=,对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
巢湖学院计算机科学与技术系,算法总体思想,对这k个子问题分别求解。
n,T（n）,=,巢湖学院计算机科学与技术系,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是:
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
凡治众如治寡，分数是也。
-孙子兵法,巢湖学院计算机科学与技术系,2.1、递归的概念,直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
下面来看几个实例。
巢湖学院计算机科学与技术系,2.1、递归的概念,例1:
阶乘函数阶乘函数可递归地定义为：
边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
巢湖学院计算机科学与技术系,2.1、递归的概念,例2:
Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。
它可以递归地定义为：
边界条件,递归方程,第n个Fibonacci数可递归地计算如下：
publicstaticintfibonacci（intn）if（n=1）return1;
returnfibonacci（n-1）+fibonacci（n-2）;
巢湖学院计算机科学与技术系,2.1、递归的概念,例3:
Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A（n，m）定义如下：
Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：
但本例中的Ackerman函数却无法找到非递归的定义。
Ackerman函数A（n，m）的自变量m的每一个值都定义了一个单变量函数：
M=0时，A（n,0）=n+2M=1时，A（n,1）=A（A（n-1,1）,0）=A（n-1,1）+2，和A（1,1）=2故A（n,1）=2*nM=2时，A（n,2）=A（A（n-1,2）,1）=2A（n-1,2），和A（1,2）=A（A（0,2）,1）=A（1,1）=2，故A（n,2）=2n。
M=3时，类似的可以推出M=4时，A（n,4）的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
巢湖学院计算机科学与技术系,2.1、递归的概念,例3Ackerman函数定义单变量的Ackerman函数A（n）为，A（n）=A（n，n）.定义其拟逆函数（n）为：
（n）=minkA（k）n.即（n）是使nA（k）成立的最小的k值。
（n）在复杂度分析中常遇到。
对于通常所见到的正整数n，有（n）4。
但在理论上（n）没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大.,巢湖学院计算机科学与技术系,2.1、递归的概念,例4:
排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。
设：
R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。
集合X中元素的全排列记为：
perm（X）。
（ri）perm（X）：
表示在全排列perm（X）的每一个排列前加上前缀得到的排列。
R的全排列可归纳定义如下：
当n=1时:
perm（R）=（r），其中r是集合R中唯一的元素；
当n1时:
perm（R）由（r1）perm（R1）,（r2）perm（R2）,（rn）perm（Rn）构成;
巢湖学院计算机科学与技术系,2.1、递归的概念,例5:
整数划分问题将正整数n表示成一系列正整数之和：
n=n1+n2+nk;
其中n1n2nk1，k1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数就是整数划分问题。
例如正整数6有如下11种不同的划分：
6；
5+1；
4+2，4+1+1；
3+3，3+2+1，3+1+1+1；
2+2+2，2+2+1+1，2+1+1+1+1；
1+1+1+1+1+1。
巢湖学院计算机科学与技术系,
（2）q（n,m）=q（n,n）,mn;
最大加数n1实际上不能大于n。
因此，q（1,m）=1。
（1）q（n,1）=1,n1;
当最大加数n1不大于1时，任何正整数n只有一种划分形式，即,（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的划分组成。
2.1、递归的概念,例5、整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p（n）为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：
将最大加数n1不大于m的划分个数记作q（n,m）。
可以建立q（n,m）的如下递归关系。
巢湖学院计算机科学与技术系,2.1、递归的概念,例5、整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
正整数n的划分数p（n）=q（n,n）。
巢湖学院计算机科学与技术系,2.1、递归的概念,例6Hanoi塔问题设a,b,c是3个塔座。
开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。
各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则：
规则1:
每次只能移动1个圆盘；
规则2:
任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则3:
在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。
巢湖学院计算机科学与技术系,当n=1时，问题比较简单。
此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。
当n1时，需要利用塔座c作为辅助塔座。
此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。
由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。
由此可以设计出解Hanoi塔问题的递归算法如下。
例6、Hanoi塔问题在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
publicstaticvoidhanoi（intn,inta,intb,intc）if（n0）hanoi（n-1,a,c,b）;
move（a,b）;
hanoi（n-1,c,b,a）;
思考题：
如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移
升级会员 