下载掌阅APP，畅读海量书库
立即打开
数据的运算是通过算法来描述的。算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。下面就从算法及其特性、算法的描述、算法的性能分析与度量三个方面对算法进行介绍。
算法（Algorithm）是对特定 问题求解步骤的一种描述 ，是 指令的有限序列 。其中每一条指令表示一个或多个操作。
一个算法应该具有下列 特性 。
1） 有穷性： 一个算法必须在有穷步之后结束，即必须在有限时间内完成。
2） 确定性： 算法的每一步必须有确切的定义，无二义性。算法的执行对应着相同的输入仅有唯一的一条路径，即相同的输入必然有相同的输出。
3） 可行性： 算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。
4） 输入： 一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。
5） 输出： 一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。
算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性 。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。此外，程序中的指令必须是计算机可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定实现。一个算法若用程序设计语言来描述，则它就是一个程序。
算法与数据结构是相辅相成的。解决某一特定类型问题的算法可以选择不同的数据结构，且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。
要设计 一个好的算法通常要考虑以下要求 。
1） 正确： 算法的执行结果应当满足预先规定的功能和性能要求。
2） 可读： 一个算法应当思路清晰、层次分明、简单明了、易读易懂。算法不仅仅是让计算机来执行的，更重要的是便于人的阅读和交流。
3） 健壮： 当输入不合法数据时，算法能够做适当处理，而不会产生莫名其妙的输出或引起其他严重的后果。
4） 高效： 算法应具有较好的时空性能。
这些指标一般很难做到十全十美，因为它们常常相互矛盾，在实际的算法评价中应根据需要有所侧重。
算法可以使用各种不同的方法来描述，最简单的方法是使用 自然语言 。用自然语言来描述算法的优点是简单且便于人们对算法的阅读，缺点是不够严谨。可以使用 程序流程图 、 N-S图 等算法描述工具，特点是描述过程简洁、明了。
用以上两种方法描述的算法不能直接在计算机上执行，若要将它转换成可执行的程序还有一个编程的问题。也可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而且也不太直观，常常需要借助注释才能使人看明白。
为了解决 理解与执行这两者之间的矛盾 ，人们使用一种称为伪码语言的描述方法来进行算法描述。 伪码语言 介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接在计算机上执行，但很容易被转换成高级语言。
本书采用类Java语言作为算法的描述工具，这使得算法的描述简洁、清晰，不拘泥于Java语言的细节，又容易转换成Java语言或C++语言的程序。
在程序设计中，对算法进行分析是非常重要的。解决一个具体的应用实例，常常有若干算法可以选用，因此程序设计者要判断哪一个算法在现实的计算机环境中对于解决该问题是最优的。在计算机科学中， 一般从算法的计算时间与所需存储空间两方面来评价一个算法的优劣 。
1.时间复杂度
将一个算法转换成程序并在计算机上执行时，其 运行所需要的时间取决于下列因素 。
1） 硬件的速度 。主要指机器的指令性能和速度，例如，64位机一般要比32位机快，主频2GHz的机器一般比1GHz的机器快。
2） 书写程序的语言 。实现语言的级别越低，其执行效率就越高，如汇编语言的执行效率一般高于高级语言，C/C++语言的执行效率一般高于Java语言等。
3） 编译程序所生成目标代码的质量 。对于代码优化较好的编译程序其所生成的目标代码的质量较高。
4） 问题的规模 。例如，求100以内的素数与求1000以内的素数其执行时间必然是不同的。
显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。因此，为了突出算法本身的性能，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。
一个算法的时间复杂度（Time Complexity）就是指算法的时间耗费，这里用T（n）表示。
一个算法执行所耗费的时间是算法中所有语句执行时间之和，而每条语句的执行时间是该语句执行一次所用时间与该语句重复执行次数的乘积。一条语句重复执行的次数称为语句的频度（Frequency Count）。
算法的时间复杂度T（n）表示为
其中，t i 表示语句i执行一次的时间；c i 表示语句i的频度。
假设每条语句执行一次的时间均为一个单位时间，那么算法的时间耗费可简单地表示为各语句的频度之和，即
【例1-5】 下面的程序段用来求两个n阶方阵A和B的乘积C。
右边注释列出了各语句的频度，因而算法的时间复杂度为
T（n）=（n+1）+n（n+1）+n 2 +n 2 （n+1）+n 3 =2n 3 +3n 2 +2n+1
可见，T（n）是矩阵阶数n的函数。
许多时候要精确地计算T（n）是困难的，很多算法的时间复杂度难以给出解析形式，或者是非常复杂的。而且当问题的规模较大时，T（n）表达式中有些项占主导地位，其他项可忽略不计。例如，在例1-5中，当n很大时，T（n）中起主导作用的是高次项“2n 3 ”，显然
T（n）与n 3 是同数量级的，T（n）可近似地用n 3 来表示。
因此，在实际应用中，往往放弃用复杂的函数来表示确切的时间复杂度，而采用一些简单的函数来近似表示时间性能，这就是时间渐进复杂度。
定义（大O记号）： 设T（n）是问题规模n的函数f（n），若存在两个正常数c和n 0 ，使得对所有的n，n≥n 0 ，有T（n）≤cf（n），则记为T（n）=O（f（n））。
例如，一个程序的实际执行时间为T（n）=20n 3 +25n 2 +9，则T（n）=O（n 3 ）。
使用大O记号表示的算法的时间复杂度，称为算法的渐进时间复杂度（Asymptotic Complexity），简称时间复杂度。
通常用O（1）表示常数计算时间。常见的渐进时间复杂度按数量级递增排列为
O（1）＜O（log 2 n）＜O（n）＜O（nlog 2 n）＜O（n 2 ）＜O（n 3 ）＜O（2 n ）
一个算法是由控制结构和基本语句构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的语句，以该基本语句重复执行的次数作为算法的时间度量。 基本运算一般应选取频度最高的语句 ，如最深层循环体内的语句。例如，在例1-5的算法中应选取“C[i][j]+=A[i][k]* B[k][j]；”作为基本操作来近似计算时间复杂度。
在有些算法中，时间复杂度不仅与问题规模相关，还与输入数据集的状态有关。对于这类问题，需要从概率的角度出发讨论。也可根据数据集可能的最好或最坏情况，估算算法的最好时间复杂度或最坏时间复杂度；或者在对数据集做某种假定的情况下，讨论算法的平均时间复杂度。
【例1-6】 冒泡排序法。
例1-6中选取交换相邻的两个元素“data[j]⇔data[j+1]；”作为基本操作。当data中序列自小到大有序时，基本操作的执行次数是0；当data中序列自大到小有序时，基本操作的执行次数是n（n+1）/2。而n个元素组成的输入集可能有n！种排列情况，若各种情况等概率，则冒泡排序法的平均时间复杂度T（n）=O（n 2 ）。
在很多情况下，输入数据集的分布概率是难以确定的，常用的方法是讨论算法在最坏情况下的复杂度，即分析算法执行时间的一个上界。因此以后的章节中，如不作特别说明时，时间复杂度是指最坏情况下的时间复杂度。
2.空间复杂度
一个算法的空间复杂度（Space Complexity）是 指算法运行从开始到结束所需的存储空间 。
算法的一次运行是针对所求解的问题的某一特定实例而言的。例如，求解排序问题的排序算法的每次执行是对一组特定个数的元素进行排序。对该组元素的排序是排序问题的一个实例。元素个数可视为该实例的特征。
算法运行所需的存储空间包括以下两部分。
1） 固定部分： 这部分空间与要处理数据的大小和个数无关，或者说与问题的实例的特征无关。固定部分主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。
2） 可变部分： 这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。
当问题的规模较大时，可变部分可能会远大于固定部分，所以一般讨论算法的渐进空间复杂度。空间复杂度的分析与时间复杂度类似，也是问题复杂度n的函数S（n），相对于渐进时间复杂度，空间复杂度也有渐进空间复杂度的概念，采用同样的大O记号，这里不再赘述。