计算机算法设计与分析第一章

1计算机算法设计与分析主讲教师：金英TheDesignandAnalysisofComputerAlgorithms2【参考教材】

王晓东,计算机算法设计与分析(第4版),电子工业出版社，2012。ThomasH.Cormen,CharlesE.Leiserson,andRonaldL.Rivest.

IntroductiontoAlgorithms(SecondEdition),

TheMITPress,2013.

[算法导论（第三版）]【课程基础】本课程要求学生在学习之前已经熟练掌握C/C++程序设计，学习过高等数学、线性代数、离散数学、概率论与数理统计、数据结构等课程。3【主要教学内容】设计算法及分析算法的理论、方法和技术；可计算问题的算法设计与分析。分为下述部分介绍：算法概述递归与分治策略动态规划贪心算法回溯法分支限界法4第一章：算法概述570年代前计算机科学基础的主题没有被清楚地认清70年代Knuth出版了《TheArtofComputerProgramming》以算法研究为主线确立了算法为计算机科学基础的重要主题1974年获得图灵奖70年代后算法作为计算机科学核心推动了计算机科学技术飞速发展算法是计算机科学的重要主题

第一节算法在计算机科学中的地位6算法设计与分析可计算理论计算复杂性理论计算机科学技术的体系解决一个计算问题的过程可计算否能行可计算否软件系统用计算机语言实现算法设计与分析算法数据结构与程序设计编译、OS、…7可计算理论计算模型可计算问题/不可计算问题计算模型的等价性--图灵/Church命题计算复杂性理论在给定的计算模型下研究问题的复杂性固有复杂性复杂性下界平均复杂性复杂性问题的分类:P=NP?公理复杂性理论8算法设计和分析设计算法的理论、方法和技术分析算法的理论、方法和技术计算机软件系统软件工具软件应用软件9

第二节算法与程序算法（Algorithm）的概念通俗地讲

算法是指解决问题的一种方法或一个过程。严格地讲

算法是由若干条指令组成的有穷序列,且满足下述性质：（1）输入:有零个或多个由外部提供的量作为算法的输入。（2）输出:算法产生至少一个量作为输出。（3）确定性:组成算法的每条指令是清晰的，无歧义的。（4）有限性:算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。10算法与程序的区别程序是算法用某种程序设计语言的具体实现；程序可以不满足算法的性质（4）----有限性。

例如:

操作系统，它是一个在无限循环中执行的程序，因而不是算法。可把操作系统的各种任务看成是一些单独的问题，每个问题由操作系统中的一个子程序通过特定的算法来实现。算法描述描述算法可以有多种形式。本课程将用C/C++语言或伪代码描述算法。11算法复杂性的含义

一个算法的复杂性的高低体现在运行该算法所需的计算机资源（主要指时间和空间资源）的多少上。

第三节算法复杂性分析

算法的复杂性主要分为:

时间复杂性空间复杂性算法的复杂性分析的用处途:

为求解一个问题选择最佳算法、最佳设备12随着计算机要解决的问题越来越复杂，规模越来越大，对求解这类问题的算法作复杂性分析具有特别重要的意义。随着计算机技术的迅速发展，对空间的要求往往不如对时间的要求那样强烈。因此我们这里的分析主要强调时间复杂性的分析。考虑时间复杂性的理由：某些用户需要提供程序运行时间的上限（用户可接受的）；所开发的程序需要提供一个满意的实时反应。13本课程考虑如下三种情况下的时间复杂度：

最坏情况；最好情况；平均情况。时间复杂性的计算方法(即估算运行时间的方法)

加、减、乘、除、比较、赋值等操作，一般被看作是基本操作，并约定所用的时间都是一个单位时间；通过计算这些操作分别执行了多少次来确定程序总的执行步数。

一般地，一些关键操作执行的次数决定了算法的时间复杂度。14例1：二分查找算法intbsearch(K,L,H){if(H<L)return(-1);else{mid=(L+H)/2;

element=A[mid];if(element==K)return(mid)；

elseif（A[mid]>K）

return(bsearch(K,L,mid-1));elsereturn(bsearch(K,mid+1,H));}2321123+T(n/2)3+T(n/2)算法时间复杂性估计：∵T(n)=2当n=0∵T(n)=11+T(n/2)当n≥1

∴T(n)=O(logn)15例2：寻找最大元素template<classT>intMax(Ta[],intn){//寻找a[0:n-1]中的最大元素

intpos=0;for(inti=1;i<n;i++)if(a[pos]<a[i])pos=i;returnpos;}算法复杂性估计：

T(n)=O(n)16渐近复杂性分析

确定程序的操作计数和执行步数的目的是为了比较两个完成同一功能的程序的时间复杂性，预测程序的运行时间随着问题规模变化的变化量。

例子:

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

进一步分析可知，渐近复杂性分析只要关心的阶就够了，不必关心包含在中的常数因子。所以，我们还可对的分析进一步简化。

设T(n)是算法A的时间复杂性函数是算法A当n→∞时的渐近时间复杂性，是T(n)中略去低阶项所留下的主项。=n217常用的渐近函数

函数名称函数名称1常数n2平方logn对数n3立方n线性2n指数nlognn倍lognn！阶乘综上分析，我们已经给出了简化算法复杂性分析的方法和步骤，即只考虑当问题的规模充分大时，算法复杂性在渐近意义下的阶。为此引入渐近符号。在那之前，首先给出常用的渐近函数。18

在下面的讨论中，用f(n)表示一个程序的时间或空间复杂性，它是问题规模n（一般是输入规模）的函数。由于一个程序的时间或空间需求是一个非负的实数，我们假定函数f(n)对于n的所有取值均为非负实数，而且还可假定n≥0。渐近记号O的定义:

f(n)=O(g(n))当且仅当存在正的常数C和n0，使得对于所有的n≥n0，有f(n)≤Cg(n)。此时，称g(n)是f(n)的一个上界。

渐近意义下的记号19例：100

=O(1):f(n)等于非零常数的情形。3n+2=O(n):

可取C＝4，n0＝2100n+6=O(n):

可取

C=101，n0＝610n2+4n+3=O(n2):

可取C=？,n0＝？6×2n+n2=O(2n):

可取C=7，n0=43×logn+2×n+n2=O(n2)n×logn+n2=O(n2)3n+2=O(n2)20三点注意事项：（1）用来作比较的函数g(n)应该尽量接近所考虑的函数f(n)。

如：3n+2=O(n2)

松散的界限；

3n+2=O(n)

较好的界限。（2）不要产生错误界限。

如:

n2+100n+6

当n<3时，n2+100n+6<106n，

由此就认为n2+100n+6＝O(n)是错误的!

事实上，对任何正常数C，只要n>C-100就有

n2+100n+6>C×n。

同理，3n2+4×2n=O(n2)是错误的界限。（3）f(n)=O(g(n))不能写成g(n)=O(f(n))。因为两者并不等价。21渐近记号

的定义：

f(n)=Θ(g(n))当且仅当存在正常数和C1，C2和n0，使得对于所有的n≥n0,有C1(g(n))≤f(n)≤

C2(g(n))。此时，称f(n)与g(n)同阶。渐近记号的定义：

f(n)=Ω(g(n))

当且仅当存在正的常数C和n0，使得对于所有的n≥n0

，有f(n)≥C(g(n))。此时，称g(n)是f(n)的下界。例：

3n+2=Θ(n)

10n2+4n+2=Θ(n2)

5×2n+n2=

Θ(2n)

22例3：非递归的折半搜索算法template<classT>intBinarySearch(Ta[],constT&x,intn){//在a[0]<=a[1]<=···<=a[n-1]中搜索x

//如果找到，则返回所在位置，否则返回–1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle–1;}return–1;

//未找到x

}算法时间复杂性估计：

while的每次循环（最后一次除外）都将以减半的比例缩小搜索范围，所以，该循环在最坏的情况下需要执行(log(n))次。

由于每次循环需耗时

(1)

，因此在最坏情况下，总的时间复杂性为

(log(n))。23第四节递归方程解的渐近阶的求法三种求递归方程解的渐近阶的方法：

(1)代入法（SubstitutionMethod）

Guessfirst,然后用数学归纳法证明.(2)迭代法(IterationMethod)

循环地展开递归方程，把递归方程转化为和式，然后可使用求和技术解之

(3)套用公式法（Mastermethod）求解型为T(n)=aT(n/b)+f(n)的递归方程24（3）套用公式法（Mastermethod）这个方法为估计形如

T(n)=aT(n/b)+f(n)的递归方程解的渐近阶提供三个可套用的公式。注：上式是一个递归方程，其中：

a≥1和b>1是常数，

f(n)是一个确定的正函数。25

这里涉及的三类情况，都是用f(n)与nlogba作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，nlogba的阶较大，

则T(n)=Θ(nlogba)。在第二类情况下，f(n)和nlogba同阶，

则T(n)=Θ(nlogbalogn)。在第三类情况下，f(n)的阶较大，

则T(n)=Θ(f(n))。

26例１：T(n)=9T(n/3)+n

此时，a=9,b=3,f(n)=n，∴nlogba

＝nlog39＝n2

可套用第一类情况得T(n)=Θ(n2)。例2：T(n)=T(2n/3)+1

此时，a=1,b=3/2,f(n)=1，∴nlogba

＝nlog3/21＝n0=1

可套用第二类情况得T(n)=Θ(logn)

。27