算法分析讲稿.doc

算法讲稿 第一部分 算法分析部分 1.1 算法概述 1.1.1 算法的基本特性 五个传统的特性 一般说来，算法必须具备以下五个重要特性 凡是一个算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称为算法，只能称为过程。值得指出的是，算法也不等于程序，算法设计也不等于程序设计，读者会逐步地体会这点，区分出二者的不同。 现在条件下的特性 好设计的目标算法基本目标/四点 正确性 基本要求! 能完成能胜任。 可读性 自己看？别人看！ 健壮性 非法数据应报错！ 高效率低存储 少占资源多干事！ 1.1.2 算法分析的目的 我们研究算法的目的是为了有效地求出问题的解，是要在计算机上运行算法。 实际上，我们只能把在相当有穷步内终止的算法投入计算机去执行，我们可以看到对某些问题尽管存在着解题的算法但并不能在计算机上实际运行，因为解题算法对计算机资源的要求已经超过了目前我们所能提供的水平。一个算法应该在有穷步终止，而作为一个有效的算法则不仅要求有穷的步骤，而且要求是很有限的步骤。 对某些问题或许存在着不同的解题算法，并且都能在计算机上实际运行，选用它们中的哪一个呢？这是需要认真思考仔细斟酌一番的。 1.1.3 算法的描述 计算机程序、自然语言、流程图、逻辑判断表、类/伪～语言…… 实际生活中，也存在着一些看似简单却难于描述的算法问题，如系鞋带这么一个简单的小孩子都会干的事，若按要求写成一个个算法步骤，恐怕真不是简单的事呢。 1.1.4 算法效率的度量 我们研究算法的目的是为了有效地求出问题的解，是要在计算机上运行算法。实际上，我们只能把在相当有穷步内终止的算法投入计算机去执行，我们可以看到对某些问题尽管存在着解题的算法但并不能在计算机上实际运行，因为解题算法对计算机资源的要求已经超出了目前我们所能提供的水平。一个算法应该在有穷步终止，而作为一个有效的算法，则不仅要求有穷的步骤,而且要求是很有限的步骤。另外，对某些问题或许存在着不同的解题算法并且都能在计算机上实际运行，应该选用它们中的哪一个呢？这是需要认真思考仔细斟酌一番的。 对算法的讨论不能只研究它是否能在有穷步骤内终止，还应对算法的运行效率做出分析。作为一个有效的算法不仅要求有穷步骤，而且要求是很有限的步骤内完成。依此判定算法的好坏，以便在已有的资源条件下作出最佳的决策。 通常采用如下五条标准，作为判定解决一类问题的最好的方法。 将算法在计算机上执行的时间减至最短。 将主存储器的需求量减至最低限度。 将算法的适应性增至最大。 将算法设计时间减至最低限度。 将算法容易理解的程度增至最大限度。 算法的正确性、简单性、最佳性和精确性等，也是评价算法的标准，但不是本书的重点，不做深入讨论。 在实际算法设计中，需要根据具体情况进行分析并加以折衷。本书主要以第一条标准来衡量一个算法的好坏，即以其在计算机上对给定输入数据所用时间复杂性作为评定标准，间或也需要较少的空间，相信读者掌握了时间复杂性的分析方法之后，不难求得给定的空间复杂性。 分析对象成立 确立分析指标 用定量来定性 1.2 算法复杂度的测度 我们分析算法的目的，是尽可能地改进算法，并且能够在一个问题上的几种可用的算法中进行选择。与之相关的几个概念我们先介绍如下。 1.2.1 几个术语 我们知道，计算机上算法是用程序来实现的。而一个程序的运行时间主要取决于这样几个因素： ·程序的数据量大小； n/N ·编译所产生的目标代码质量； 32bits/128bis ·执行程序使用的机器指令性质、速度； PⅡ/ PⅢ/ADM ·程序表示的算法的时间复杂度。 顺序/递归/循环 假定：· 对一个程序来说，输入数据量的多少虽然产生不同的运行时间，但是本书中假定，对于解同一问题的各种算法来说，其输入数据量是相同的。 · 至于编译产生的目标代码质量问题，我们假设使用的是同一种语言，则编译质量自然一致了。 · 机器指令的功能大小，对于程序执行起来的时间是有直接关系的，引入了多项式相关的概念之后，具体指令的速度对算法的影响也不是最主要的因素了。 真正影响一个程序运行时间的，是解决给定问题的算法质量如何。它编制的好就运行时间短，占用内存少；反之则多费时间，多耗空间。为了使大家对此有一个感性认识，我们以大家熟悉的排序问题为例。今要将1000个杂乱无章的整数按照从小到大的顺序排列出来，对此问题，我们可以用许多方法来处理，但是，各种方法所需要的时间是大大