1.2.3 算法的特性与算法的描述
1．算法的定义
算法（Algorithm）是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。操作序列包括了一组操作，每一个操作都完成特定的功能。例如求n个数中最大者的问题，其算法描述如下。
（1）定义一个变量max和一个数组a［］，分别用来存放最大数和数组的元素，并假定第一个数最大，赋给max。
max=a[0];
（2）依次把数组a中其余的n-1个数与max进行比较，遇到较大的数时，将其赋给max。
最后，max中的数就是n个数中的最大者。
算法的描述可采用自然语言描述、伪代码或称为类语言描述、程序流程图及程序设计语言（如C语言）。其中，采用自然语言描述容易产生歧义，伪代码形式或C、C++、Java等语言描述方便在计算机上运行，不会产生歧义性。
2．算法的五大特性
（1）有穷性。有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
（2）确定性。算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，也就是相同的输入只能有一个唯一的输出结果，而不会出现输出结果的不确定性。
（3）可行性。算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
（4）输入。算法具有零个或多个输入。
（5）输出。算法至少有一个或多个输出。输出的形式可以是打印输出，也可以是返回一个或多个值。
3．算法分析
一个好的算法往往会带来程序运行效率高的好处，算法效率和存储空间需求是衡量算法优劣的重要依据。
（1）算法设计的要求
一个好的算法应该具备以下目标：
● 正确性：算法的正确性是指算法至少应该是输入、输出和加工处理无歧义性，并能正确地反映问题的需求，能够得到问题的正确答案。
● 可读性：算法设计的目的首先是人们的阅读、理解和交流，其次才是计算机执行。可读性有助于人们对算法的理解，晦涩难懂的算法往往隐含错误不易被发现，并且调试和修改困难等问题。
● 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
● 高效率和低存储量：效率指的是算法的执行时间。对于同一个问题如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指的是算法在执行过程中需要的最大存储空间。设计算法时，应尽量选择高效率和低存储量需求的算法。
（2）算法时间复杂度
算法执行时间需通过依据该算法编制的程序在计算机上的运行时所耗费的时间来度量，而度量一个算法在计算机上的执行时间通常有如下两种方法。
● 事后统计方法：目前计算机内部大都有计时功能，有的甚至可精确到毫秒级，不同算法的程序可通过一组或若干组相同的测试程序和数据以分辨算法的优劣。但是，这种方法有两个缺陷，一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的长短依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。因此，人们常常采用事前分析估算的方法评价算法的好坏。
● 事前分析估算方法：这主要在计算机程序编制前，对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素。
算法采用的策略、方法。
编译产生的代码质量。
问题的规模。
书写的程序语言，对于同一个算法，语言级别越高，执行效率越低。
机器执行指令的速度。
在以上5个因素中，算法采用的不同的策略，或不同的编译系统，或不同的语言实现，或在不同的机器运行时，效率都不相同。抛开以上因素，算法效率则可以通过问题的规模来衡量。
一个算法由控制结构（顺序、分支和循环结构）和基本语句（赋值语句、声明语句和输入输出语句）构成，则算法的运行时间取决于两者执行时间的总和，所有语句的执行次数可以作为语句的执行时间的度量。语句的重复执行次数称为语句频度。
例如，斐波那契数列的算法和语句的频度如下。
每一条语句的右端是对应语句的频度（frequency count），即语句的执行次数。上面算法总的执行次数为T（n）=1+1+1+n+4（n-1）=5n-1。
①算法的时间复杂度定义
在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作T（n）=O（f（n））。
它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度（Asymptotic Time Complexity），简称为时间复杂度。其中，f（n）是问题规模n的某个函数。
常用的时间复杂度所耗费的时间从小到大依次是O（1）<O（log2n）<O（n）<O（n2）<O（n3）<O（2n）<O（n!）。
②算法时间复杂度分析举例
一般情况下，算法的时间复杂度只需要考虑算法中的基本操作，即算法中最深层循环体内的操作。
【例1-1】分析以下程序段的时间复杂度。
该程序段中的基本操作是第二层for循环中的语句，即k++，其语句频度为n+（n-1）+（n-2）+…+1=n（n+1）/2。因此，其时间复杂度为O（n2）。
【例1-2】分析以下算法的时间复杂度。
该函数fun（）的基本运算是x=x*2，设执行时间为T（n），则2T（n）≤n/2，则有T（n）≤log2。因此，时间复杂度为O（log2n）。
【例1-3】一个算法所需时间由以下递归方程表示，分析算法的时间复杂度。
根据以上递归方程，可得
因此，该算法的时间复杂度为O（n!）。
这其实是求n！的算法的时间复杂度表示，它是将规模为n的问题划分为规模为n-1的问题，再进一步缩小问题规模，直至规模为1为止。
【例1-4】分析以下算法的时间复杂度。
该算法中的基本操作是while循环中的语句，设while循环次数为f（n），则变量i从0到f（n），因此循环次数为f（n）*（f（n）+1）/2≤n，则
，故时间复杂度为
。
（3）算法空间复杂度
空间复杂度（Space Complexity）作为算法所需存储空间的量度，记作S（n）=O（f（n））。其中，n为问题的规模，f（n）为语句关于n的所占存储空间的函数。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为O（1）。
【例1-5】以下是一个简单选择排序算法，分析算法的空间复杂度。
该算法借助了变量t，与问题规模n的大小无关，空间复杂度为O（1）。
【例1-6】以下算法是求n个数中的和，分析算法的空间复杂度。
设RevNum（n）占用的临时空间为S（n），由以上算法可得到以下占用临时空间的递推式。
则有S（n）=S（n/10）+1=S（n/102）+1+1=…=S（n/10c）+c。设当n/10c=1时，即c=log10n，有S（n）=log10n+1，因此，该算法的空间复杂度为O（log10n）。