全屏显示专题章节

求解同一个问题,可以有许多不同的算法,那么,怎样来衡量这些算法的优劣呢？首要的条件是选用的算法必须是正确的,其次则应考虑以下三个方面。

（1）执行算法所耗费的时间。

（2）执行算法所占用的内存开销（主要考虑占用的辅助存储空间）。

（3）算法应易于理解、易于编码、易于调试等。

一个算法执行时所耗费的时间,从理论上来讲是无法计算出来的,必须上机测试才能知道,但实际上不可能也没有必要对每个算法都上机测试（因为计算机的运行速度与CPU等因素有关,同一算法在不同的计算机上运行的时间是不同的）,只需要知道在相同条件下,哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比,哪个算法中语句执行次数多,它所花费的时间就多。

语句频度是指该语句在一个算法中重复执行的次数,一个算法的时间耗费是该算法中所有语句频度之和。

【例1－6】　分析以下算法的语句频度。

【分析】　语句（1）的循环控制变量i从0增加到n,测试条件i＝n成立时才终止,故它的语句频度是n＋1,但是其循环只能执行n次。语句（2）作为语句（1）的循环体应该执行n次,但语句（2）的循环控制变量j从1增加到n＋1,当测试条件j＝n＋1成立时才终止,故其语句频度是n（n＋1）。同理,可得语句（3）的频度为n²。

该算法中所有语句频度之和（即算法的时间耗费）为:

在上面提到的时间频度中,n称为问题规模,当n不断变化时,时间频度T（n）也会不断变化。但为了弄清它变化时有什么规律,因此引入了时间复杂度概念。

设T（n）的一个辅助函数为f（n）,定义当n大于等于某一个足够大的正整数n时,存在正的常数C,使得当n≥n₀时都满足0≤T（n）≤Cf（n）,则称f（n）是T（n）的同数量级函数。把T（n）表示成数据量级的形式为:

其中,大写字母O为英文Order（数量级）一词的第一个字母。其含义是,当问题规模n足够大时,算法的执行时间T（n）与函数f（n）成正比。因此,定义时间复杂度为

如果算法的执行时间T（n）与问题规模n无关,是一个常数,则记作T（n）＝O（1）。

通常情况下,随着n的增大,T（n）的增长较慢的算法为最优的算法。

【例1－7】　在下列三段程序段中,给出原操作x＝x＋1的时间复杂度分析。

其时间复杂度为O（1）,可将其称为常量阶。

（2）for(i=1;i<=n;i++)x=x+1;

其时间复杂度为O（n）,可将其称为线性阶。

其时间复杂度为O（n²）,可将其称为平方阶。

【例1－8】　下列程序段是一个二重循环,试分析语句x＋＋的执行频度。

其执行频度为n＋（n－1）＋（n－2）＋…＋3＋2＋1＝n（n＋1）/2

而该语句执行次数关于n的增长率为n²,即其时间复杂度为O（n²）。

此外,算法还能呈现的时间复杂度有对数阶O（log₂n）,指数阶O（2ⁿ）等。

数据结构中常用的时间复杂度频率计数有以下7种。

（1）O（1）,表示常数型。

（2）O（n）,表示线性型。

（3）O（n²）,表示平方型。

（4）O（n³）,表示立方型。

（5）O（2ⁿ）,表示指数型。

（6）O（log₂n）,表示对数型。

（7）O（nlog₂n）,表示二维型。

不同数量级的时间复杂度的曲线如图1－7所示,表1－3与图1－3是同一问题的不同表示形式。一般情况下,随着n的增大,T（n）增长较慢的算法为最优的算法。从中应该选择使用多项式阶O（n^k）的算法,而避免使用指数阶的算法。

3.最坏时间复杂度

算法中基本操作重复执行的次数还与问题的输入数据集有关。

【例1－9】　分析以下语句的时间复杂度。

此算法中,语句②的频度不仅与问题规模n有关,还与数组中各元素的值（k值）有关。

（1）最好的情况下,数组最后一个元素的值等于k,则语句②的频度f（n）是常数0,时间复杂度为O（1）。

（2）最坏的情况下,数组中各元素的值都不等于k,则语句②的频度f（n）＝n,时间复杂度为O（n）。

最坏情况下的时间复杂度称为最坏时间复杂度,一般不作特别说明的情况下,讨论的时间复杂度都是最坏时间复杂度。这是因为,最坏时间复杂度是算法在任何输入实例上运行时间的上限,这就保证了算法的运行时间不会比这一时间更长。因此,例1－9中算法的时间复杂度为:T（n）＝O（n）。

由于数据实际占用空间与计算机的软件（编译系统）、硬件（字长等）密切相关,故数据实际占用空间的多少难以相互关联。以整型数据为例,有些系统中长度为2字节,而另外有些系统中长度为4字节。算法空间分析度量的标准并不是计算实际占用空间,而是计算整个算法的辅助存储单元个数。

关于算法的存储空间需求的分析,类似于算法的时间复杂度,可采用空间复杂度作为算法所需存储空间的量度,表示为如下形式。

若算法执行时间所需要的辅助空间相对于输入数据量而言是一个常数,则称这个算法为原点空间,辅助空间为O（1）。

1.数据结构研究的是数据的表示形式及数据之间的相互关系。从逻辑结构来看,数据结构包括集合、线性结构、非线性结构等。从存储结构来看,数据结构包括顺序存储、链式存储、索引存储和散列存储四种。

2.集合中不存在数据之间的关系；线性结构的数据元素之间存在着一对一的关系；树型结构的数据元素之间存在着一对多的关系；图型结构的数据元素之间存在着多对多的关系。

3.顺序存储相当于C语言中的一维数组存储；链式存储相当于C语言中的链表存储；索引存储也称为索引查找,包括主表和索引表；散列存储也称为数据查找,是用构造函数的方法得到关键字的地址。

4.算法的评价指标首先是正确性,然后是健壮性、可读性、高效率和低存储量。

5.时间复杂度和空间复杂度通常采用数量级的形式来表示,若一个算法的时间复杂度和空间复杂度越优,则算法的执行效率就越高。