文件名称：算法性能的分析与评价-一种新的超宽带脉冲波形设计方法
文件大小：3.72MB
文件格式：PDF
更新时间：2024-07-09 04:02:50
数据结构
第一章 算法及其复杂度 §1.2 算法性能的分析与评价 8 §1.2 算法性能的分析与评价 1.2.1 三个层次 相信本书的读者，都已学习并掌握了至少一种程序设计语言，比如 Java。学习程序设计语言的 目的，就是学会如何编写合法的程序。这里所说的“合法”，指的是合乎该语言的语法，从而保证所 编写的程序能够顺利通过编译器生成可执行代码，或者能够通过解释器解释执行。从利用计算机解 决实际问题的角度来看，这只是第一个层次，当然也是 基本的要求。 对于算法而言，前面提到的有穷性应该是一项起码的要求，然而遗憾的是，合法的程序却未必 满足有穷性⎯⎯相信大多数读者都曾编写过导致无穷循环或者递归溢出的合法程序。 实际上，我们不仅需要确定算法对任何输入都能够在有穷次操作后终止并输出结果，而且希望 等待的时间尽可能地短。为此，我们首先需要确立一种尺度，以度量不同算法的效率（执行速度）； 另外，我们还需要学习如何设计和使用适宜的数据结构，编写出效率高、能够处理大规模数据的程 序。这些都属于第二层次的问题。前一问题将通过对算法分析理论的学习来解决，后一问题则需要 通过对算法设计技巧以及相应的数据结构的学习来解决，这些也正是本书的主题。 如果将借助计算机解决实际问题比作书法，那么在第一层次上就相当于学习点、横、竖、撇和 捺等基本笔画，而第二层次则相当于学习如何将不同的笔画按照一定的间架结构组成有意义的不同 汉字。然而这还远远不够，作为一幅完整的书法作品，还需要在汉字之间形成大小、粗细、疏密、 浓淡、奇正及枯润等方面的搭配与呼应，也就是要讲求章法。在利用计算机解决实际问题的过程中， 同样存在这样一个更高层次的问题：倘若软件的规模大到任何个人或少数人都不足以 发出来地步， 而且在其生命期内软件也需要很多人的协作才能得以维护，则需要进一步考虑一些更为全局性的问 题，这些问题都属于软件工程学的范畴，本书将不做深入介绍。 1.2.2 时间复杂度及其度量 我们首先来解决第二层次的前一个问题：如何度量一个算法的执行速度并评价其效率？具体地， 对于不同的输入，算法需要运行多少时间才能得出结果？ 问题规模、运行时间及时间复杂度 直接回答上述问题并非易事，原因在于，即使是同一算法，针对不同的输入运行的时间并不相 同。以排序问题为例，输入序列的规模、组成和次序都不是确定的，这些因素都会影响到排序算法 的运行时间。在所有这些因素中，输入的规模是 重要的一个。还是以排序问题为例，如果是操作 系统对某一文件夹内的文件按名字排序，则输入的规模通常不超过 100，故可以在瞬间完成排序； 反之，若需要对全中国人口普查的数据进行排序，则输入的规模将高达 109，此时若采用起泡算法， 恐怕需要经过数月甚至数年才能完成排序。 因此，为了简化分析，我们通常只考虑输入规模这一主要因素。如此一来，本节 头所提出的 问题就转化为：针对不同规模的输入，算法的执行时间各是多少？如果将某一算法为了处理规模为 n 的问题所需的时间记作 T(n)，那么随着问题规模 n 的增长，运行时间 T(n)将如何增长？我们将 T(n) 称作算法的时间复杂度。