1.5.2 算法时间复杂度
算法分析的目的是看设计的算法是否具有可行性，并尽可能挑选运行效率高的算法。
1.两种算法时间性能分析方法
衡量一个算法在计算机上的执行时间通常有以下两种方法。
（1）事后统计方法
这种方法主要是通过设计好的测试程序和数据，利用计算机的计时器对不同算法编制好的程序比较各自的运行时间，从而确定算法效率的好坏。但是，这种方法有三个缺陷：一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的比较依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣；三是算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大的关系，效率高的算法在小的测试数据面前往往得不到体现。
（2）事前分析估算方法
这主要在计算机程序编制前，对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素：
a.算法采用的策略、方法；
b.编译产生的代码质量；
c.问题的规模；
d.书写的程序语言，对于同一个算法，语言级别越高，执行效率越低；
e.机器执行指令的速度。
在以上五个因素中，算法采用不同的策略，或不同的编译系统，或不同的语言实现，或在不同的机器运行时，效率都不相同。抛开以上因素，仅考虑算法本身的效率高低，可以认为一个算法的效率仅依赖于问题的规模。因此，通常采用事前分析估算方法衡量算法的效率。
2.问题规模和语句频度
抛开硬件因素，问题规模和算法的策略成为影响算法效率的主要因素。问题规模是算法求解问题输入量的多少，是问题大小的表示，一般用整数n表示。对不同的问题，问题规模n有不同的含义。例如，对于矩阵运算，n为矩阵的阶数；对于多项式运算，n为多项式的项数；对于图的有关运算，n为图中顶点的个数。显然，对于同一个问题，n取值越大，算法的执行时间会越长。
算法的时间分析度量标准不是执行实际算法的具体运行时间，而是算法中所有语句的执行时间总和。一个算法由控制结构（顺序、分支和循环结构）和基本语句（赋值语句、声明语句和输入输出语句）构成，则算法的运行时间取决于两者执行时间的总和。一条语句的执行时间等于该条语句的重复执行次数和执行一次语句所需时间的乘积，其中一条语句的重复执行次数称为语句频度（Frequency Count）。而语句执行一次所需时间是与机器的配置、编译程序质量等密切相关的，算法分析并非精确计算算法的实际执行时间，而是对算法的语句执行次数进行估计。对于问题规模为n的语句，其语句频度可表示为f（n），也就是说，算法的执行时间与f（n）成正比。
例如，两个n×n矩阵相乘的算法和语句的频度如下。
每一条语句的最右端是对应语句的频度，即语句的执行次数。上面算法总的执行次数为f（n）=n+n2+n2+n3+n3=2n3+2n2+n。
3.算法时间复杂度定义
对于较为复杂的算法来说，语句的频度难以直接表示，或者语句的频度虽可用数学公式表示出来，但可能是一个非常复杂的函数。因此，为了客观反映一个算法的执行时间，通常将算法中的基本操作语句重复执行的频度作为度量标准，所谓基本操作语句是指算法中重复执行次数和算法的执行时间成正比的语句，它是对算法执行时间贡献最大的语句。对于上面两个矩阵相乘的算法，当n趋向于无穷大时，有
当n充分大时，f（n）与n3的比是一个不为零的常数，即f（n）与n3是同阶的，两者处于同一数量级（Order of Magnitude）。这里，用“O”表示数量级。可记作T（n）=O（f（n））=O（n3）。由此可得算法时间复杂度定义如下：
算法的时间复杂度（Time Complexity），即算法的时间量度，就是算法中基本操作语句（贡献最大的语句）执行的次数是问题规模n的某个函数f（n），记作：
T（n）=O（f（n））
它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。实际上，算法的时间复杂度分析是一种时间增长趋势分析。
上述公式的含义是为T（n）找到一个上界，T（n）=O（f（n））是指存在着正常量c和一个足够大的正整数n0，使得n≥n0，有0≤T（n）≤cf（n）。T（n）的上界可能有多个，通常只保留最高阶，忽略其低阶和常系数。例如，f（n）=2n3+2n2+n，则T（n）=O（n3）。
一般情况下，随n的增大，T（n）的增长较慢的算法为最优的算法。例如，在下列三段程序段中，给出基本操作x=x+1的时间复杂度分析。
一般情况下，一个没有循环或者循环次数与问题规模n无关的算法，记作O（1），称为常量阶。程序段（1）的时间复杂度为O（1）；程序段（2）的时间复杂度为O（n），我们把它称为线性阶；程序段（2）的时间复杂度为O（n2），我们把它称为平方阶。此外算法的时间复杂度还有对数阶O（log2n）、指数阶O（2n）等。
常用的时间复杂度所耗费的时间从小到大依次是：O（1）<O（log2n）<O（n）<O（n2）<O（n3）<O（2n）<O（n!）<O（n!）。
算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，具有指数级的时间的复杂度算法只有当n足够小时才是可使用的算法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度算法是常用的算法。一些常用的时间复杂度频率表如表1.2所示。
表1.2 常用的时间复杂度频率表
一些常见函数的增长率如图1.10所示。
图1.10 常见函数的增长率
4.算法时间复杂度分析举例
一般情况下，算法的时间复杂度只需要考虑算法中的基本操作，即算法中最深层循环体内的操作。
【例1.1】 分析以下程序段的时间复杂度。
该程序段中的基本操作是第二层for循环中的语句，即x++和a[i][j]=x，其语句频度为（n-1）（n-2）/2。因此，其时间复杂度为O（n2）。
【例1.2】 分析以下算法的时间复杂度。
该函数fun（）的基本运算是i=i*2，设执行时间为T（n），则2T（n）≤n，有T（n）≤log2n=O（log2n）。因此，时间复杂度为O（log2n）。
【例1.3】 分析以下算法的时间复杂度。
该算法中的基本操作是while循环中的语句，设while循环次数为f（n），则变量i为从0到f（n），因此循环次数为f（n）*（f（n）+1）/2≤n，则
，根据时间复杂度定义，T（n）≤cf（n），故时间复杂度为
。
【例1.4】 一个算法所需时间由以下递归方程表示，分析算法的时间复杂度。
根据以上递归方程，可得T（n）=2T（n-1）+1=2（2T（n-2）+1）+1=22T（n-2）+2+1
=22（2T（n-3）+1）+2+1
=……
=2k-1（2T（n-k）+1）+2k-2+…+2+1
=……
=2n-2（2T（1）+1）+2n-2+…+2+1
=2n-1+…+2+1
=2n-1
因此，该算法的时间复杂度为O（2n）。
在有些情况下，算法的基本操作的重复执行次数还依赖于输入的数据集。例如，在以下的冒泡排序算法中：
基本操作是交换相邻数组中的整数部分。当数组a中的初始序列为从小到大有序排列时，基本操作的执行次数为0；当数组中初始序列为从大到小排列时，基本操作的执行次数为n（n-1）/2。对这类算法的分析，一种方法是计算所有情况的平均值，这种计算方法称为平均时间复杂度；另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。上述冒泡排序时的平均时间复杂度和最坏时间复杂度分别为T（n）=O（n2）。一般情况下，在没有特殊说明情况下，指的都是最坏时间复杂度。