算法设计与分析 第1章

《算法设计与分析 第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析湖南人文科技学院计算机系授课：肖敏雷邮箱：minlei_xiao@126.com关于本课程课程目的：计算机算法设计与分析导引不是一门试验或程序设计课程也不是一门数学课程教材：计算机算法设计与分析-王晓东前导课：数据结构+程序设计参考资料：算法设计与分析—C++语言描述陈慧南编电子工业出版社计算机算法基础(第三版)余祥宣华中科技大学本课程的主要任务算法学习将涉及5个方面的内容：1）设计算法：创造性的活动2）表示算法：思想的表示形式3）确认算法：证明算法的正确性程序的证明4）分析算法：算法时空特性

2、分析5）测试程序：调试和作出时空分布图本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础第1章算法概述学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。算法的研究内容问题是否可解1930’s研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：Postmac

3、hines、Turingmachines等。这一阶段的成果是：大部分问题为不可解。高效率的解决方法随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。算法的五个重要特性（其他教材的描述）确定性、能行性、输入、输出、有穷性1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。例：不符合确定性的运算5/0将6或7与x相加2）能行性（教材中没有）算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成；它们可以通过已经实现的基本运算执行有限次来实现

4、。例：整数的算术运算是“能行”的实数的算术运算是“不能行”的，某些实数只能由无限长的十进制数表示，像这样的2个数相加就违背了能行性这一特性。3）输入每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合——定义域（或值域）4）输出一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。5）有穷性一个算法总是在执行了有穷步的运算之后终止。程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)（有限性）。例如操作系统，是一个在无限循环中执行

5、的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法算法复杂性分析算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。算法的时间复杂性（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)

6、size(I)=n}（2）最好情

7、况下的时间复杂性Tmin(n)=min{T(I)

8、size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。算法渐近复杂性对于：T(n),asn;如果存在：(T(n)-t(n))/T(n)0，asn;就称：t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。比如：当T(n)＝３n2+4nlogn+7时，t(n)的一个答案是３n2介绍几个渐近分

9、析的记号大O记号(上界)记号(下界)记号(同阶)小o记号（低阶）1大O记号定义1设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n)=O(g(n))，称为大O记号（bigOhnotation）。一个算法具有O(g(n))的运行时间，是指当n足够大时，算法的运行时间不超过g(n）的常数倍，g(n)是它的一个上界。例1f(n)=2n+3=O(n)当n≥3时，2n+3≤3n，所以，可选c=3，n0=3。对于n≥n0，f(n

10、)=2n+3≤3n，所以，f(n)=O(n)，即2n+3O(n)。这意味着，当n≥3时，例1的程序步不会超过3n，2n+3=O(n)。例2f(n)=10n2+4n+2=O(n2)对于n≥2时，有10n2+4n+2≤10n2+5n，并且当n≥5时，5n≤n2，因此，可选c=11,n0=5；对于n≥n0，f(n)=10n2+4n+2≤11n2，所以f(n)=O(n2)。例3f(n)=n！=O(nn)对于n≥1，有n