《黑龙江大学计算机算法设计与分析--第一章》由会员分享，可在线阅读，更多相关《黑龙江大学计算机算法设计与分析--第一章（28页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析主讲教师：金英The Design and Analysis of Computer Algorithms1【参考教材】 王晓东,计算机算法设计与分析 (第3版) ,电子工业出版 社，2007。 Thomas H.Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms (Second Edition), The MIT Press, 2002. 算法导论 （第二版）【课程基础】 本课程要求学生在学习之前已经熟练掌握C/C+程序 设计，学习过高等数学、线性代数、离散数学、概率
2、论 与数理统计、数据结构等课程。2【主要教学内容】设计算法及分析算法的理论、方法和技术； 可计算问题的算法设计与分析。 分为下述部分介绍： 算法概述 递归与分治策略 动态规划 贪心算法 回溯法 分支限界法3第一章：算法概述4 70年代前 计算机科学基础的主题没有被清楚地认清 70年代 Knuth出版了The Art of Computer Programming 以算法研究为主线确立了算法为计算机科学 基础的重要主题 1974年获得图灵奖 70年代后 算法作为计算机科学核心推动了计算机科学 技术飞速发展技术飞速发展算法是计算机科学的重要主题第一节 算法在计算机科学中的地位5算法设计与分析可计算
3、理论计算复杂性理论计算机科学技术的体系计算机科学技术的体系解决一个计算问题的过程可计算否能行可计算否软件系统用计算机语言实现算法设计与分析算法数据结构与程序设计编译、OS、 6 可计算理论 计算模型 可计算问题/不可计算问题 计算模型的等价性-图灵/Church命题 计算复杂性理论 在给定的计算模型下研究问题的复杂性 固有复杂性 复杂性下界 平均复杂性 复杂性问题的分类: P=NP? 公理复杂性理论7算法设计和分析 设计算法的理论、方法和技术 分析算法的理论、方法和技术计算机软件 系统软件 工具软件 应用软件8第二节 算法与程序 算法（Algorithm）的概念 通俗地讲算法是指解决问题的一种
4、方法或一个过程。 严格地讲算法是由若干条指令组成的有穷序列,且满足下述性质： （1）输入: 有零个或多个由外部提供的量作为算法的输入。 （2）输出: 算法产生至少一个量作为输出。 （3）确定性: 组成算法的每条指令是清晰的，无歧义的。 （4）有限性: 算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。9算法与程序的区别 程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的性质（4）-有限性。例如:操作系统，它是一个在无限循环中执行的程序，因 而不是算法。可把操作系统的各种任务看成是一些单 独的问题，每个问题由操作系统中的一个子程序通过 特定的算法来实现。 算法描述 描述
5、算法可以有多种形式。 本课程将用C/C+语言或伪代码描述算法。10算法复杂性的含义一个算法的复杂性的高低体现在运行该算法 所需的计算机资源（主要指时间和空间资源） 的多少上。第三节 算法复杂性分析 算法的复杂性主要分为: 时间复杂性空间复杂性 算法的复杂性分析的用处途: 为求解一个问题选择最佳算法、最佳设备11随着计算机要解决的问题越来越复杂，规模 越来越大，对求解这类问题的算法作复杂性分 析具有特别重要的意义。随着计算机技术的迅速发展，对空间的要求 往往不如对时间的要求那样强烈。因此我们这 里的分析主要强调时间复杂性的分析。考虑时间复杂性的理由： 某些用户需要提供程序运行时间的上限（用户 可
6、接受的）； 所开发的程序需要提供一个满意的实时反应。12本课程考虑如下三种情况下的时间复杂度：最坏情况；最好情况；平均情况。 时间复杂性的计算方法(即估算运行时间的方法)加、减、乘、除、比较、赋值等操作，一般被看 作是基本操作，并约定所用的时间都是一个单位时 间；通过计算这些操作分别执行了多少次来确定程 序总的执行步数。一般地，一些关键操作执行的次数决定了算法 的时间复杂度。13例1：二分查找算法int bsearch(K,L,H) if (HK） return(bsearch(K,L, mid-1) ; else return(bsearch(K, mid+1,H);232 1 1 23+T
7、(n/2)3+T(n/2)算法时间复杂性估计： T(n)=2 当n=0 T(n)=11+T(n/2) 当n1 T(n) = O(log n)14例2：寻找最大元素template int Max(T a, int n) /寻找a0:n-1中的最大元素 int pos=0; for (int i=1; iC-100就有n2+100n+6Cn。同理，3n2+42n=O(n2)是错误的界限。 （3）f(n)=O(g(n)不能写成g(n)=O(f(n)。因为两者并不等价。20 渐近记号 的定义：f(n)=(g(n)当且仅当存在正常数和C1，C2和n0， 使得对于所有的nn0, 有C1(g(n)f(n)
8、 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) 52n +n2= (2n) 21例3：非递归的折半搜索算法templateint BinarySearch(T a , const Telse right=middle 1;return 1; /未找到x算法时间复杂性估计：while的每次循环（最后一次除外）都将 以减半的比例缩小搜索范围，所以，该循 环在最坏的情况下需要执行 (
9、log(n)次。由于每次循环需耗时 (1) ，因此在最坏 情况下，总的时间复杂性为 (log(n)。22第四节 递归方程解的渐近阶的求法三种求递归方程解的渐近阶的方法：(1)代入法（Substitution Method）(2)迭代法 (Iteration Method)(3)套用公式法（Master method）23（3）套用公式法（Master method）这个方法为估计形如T(n)=aT(n/b)+f(n) 的递归方程解的渐近阶提供三个可套用的公式。 注：上式是一个递归方程，其中：a1和b1是常数，f(n)是一个确定的正函数。24这里涉及的三类情况，都是用f(n)与nlogba作比
10、较。定理直观地告诉我们，递归方程解的渐近 阶由这两个函数中的较大者决定。在第一类情况下， nlogba的阶较大，则T(n)=(nlogba)。在第二类情况下， f(n)和nlogba同阶 ，则T(n)=(nlogbalogn) 。在第三类情况下，f(n)的阶较大，则T(n)=(f(n)。 25例： 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)
11、。26例：T(n)=T(n/)+nlogn此时，a=3,b=4,f(n)=nlogn，nlogba nlog43 O(n0.793)可套用第三类情况得T(n)= (nlogn)。例： T(n)=T(n/)+nlogn （本方法对之无能为力的例子）此时，a=,b=,f(n)=nlogn， nlogba nlog22n此时f(n)在第二类情况和第三类情况的间隙 里，本方法对它无能为力。27注意：在第一类情况下， f(n)的阶不仅必须比nlogba的 阶小，而且必须是多项式地比 nlogba的阶小，即 f(n)必须渐近地小于nlogba与n-的积，是某个正 常数。在第三类情况下， f(n)的阶不仅必须比nlogba的 阶大，而且必须是多项式地比 nlogba的阶大，即 f(n)必须渐近地大于nlogba与n+的积，是某个正 常数。28
