2.算法时间复杂度分析

（1）计算算法的频度

（2）频度编辑用“O”表示

（3）简化的算法时间复杂度分析

（4）时间复杂度的求和、求积定理

前言

在一个算法设计好之后，还需要对其进行分析，确定一个算法的优劣。本节讨论算法的时间复杂度和空间复杂度分析。

一、算法分析概述

算法分析就是分析算法占用计算机资源的多少。而计算机资源主要是CPU时间和内存空间，分析算法占用CPU时间的多少称为时间性能分析，分析算法占用空间的多少称为空间性能分析。

算法分析的目的是分析算法的时空性能以便改进算法。

二、算法时间性能分析

1.两种算法时间性能分析

通常有两种衡量算法时间性能的方法，即事后统计法和事前估算法。

事后统计法：编写算法对应程序，统计其执行时间。一个算法用计算机语言实现后，在计算机上执行所消耗的时间与很多因素有关，如计算机的运行速度、编写程序采用的计算机语言、编译产生的机器代码质量和问题的规模问题。这种方法存在两个。一是必须执行程序，二是存在很多因素掩盖了算法本质
事前估算法：撇开这些与计算机硬件、软件有关的因素，仅考虑算法本身的效率高低，可以认为一个特定算法的“运行工作量”的大小只依赖于问题的规模（通常用整数n表示），或者说算法的执行时间是问题规模的函数，因此后面主要采用事前估算法来分析算法的时间性能

2.算法时间复杂度分析

（1）计算算法的频度 $T(n)$

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的。例如，在以下算法中，语句1、3、5和6就是原操作。

而算法的执行时间取决于控制结构和原操作的综合效果。显然，在一个算法中执行原操作数的次数越少，其执行时间也就相对较少；执行原操作数次数越多，其执行时间也就相对越多。也就是说，一个算法的执行时间可以由其中原操作数的执行次数来计量。

假设算法的问题规模为n，如果对10个整数排序，问题规模n就是10。算法时间分析的就是求出算法所有原操作数的执行次数（也成为频度），它是问题规模n的函数，用 $T(n)$ 表示。

算法执行时间大致等于原操作所需的时间 $*T(n)$ ，也就是说 $T(n)$ 与算法的执行时间成正比，为此用 $T(n)$ 表示算法的执行时间，比较不同算法的 $T(n)$ 大小得出算法执行时间的多少。

（2）频度 $T(n)$ 用“O”表示

由于算法分析不是绝对是件的比较，在求出 $T(n)$ 后，通常进一步采用时间复杂度来表示。算法时间复杂度（time complexity）就是用 $T(n)$ 的数量级来表示，记作 $T(n)=O(f(n))$ 。

在上述表达式中“O”读作“大O”（是Order的简写，意指数量级），其含义是为 $T(n)$ 寻找一个上界 $f(n)$ ，其严格地数学定义是 $T(n)$ 的数量级表示为 $O(f(n))$ ，是指存在着正常量 $c,n_{0}$ (为一个足够大的整数)，使得 $\lim_{n\rightarrow n_{0}}\frac{\left | T(n) \right |}{\left | f(n) \right |}=c\neq 0$ 成立。所以算法时间复杂度也成为渐进时间复杂度，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。因此算法时间复杂度实际上是一种时间增长趋势分析。

显然， $T(n)$ 的这种上界f(n)可能有多个，通常取最近凑的上界。也就是只求出 $T(n)$ 的最高阶，忽略其低阶项和常数系数，这样既可简化 $T(n)$ 的计算，又能比较客观地反映出当m很大时算法的时间性能。例如，对于【例1.6】有 $T(n)=2n^2+2n+1=O(n^2)$ ，也就是说，该算法的时间复杂度为 $O(n^2)$ 。

一般情况下，一个没有循环（或者有循环，但循环次数与问题规模n无关）地算法中原操作数执行次数与问题规模n无关，记作 $O(1)$ ，也成为常数阶。算法中的每个简单语句，例如定义变量语句、赋值语句和输入输出语句，其执行时间都看成是 $O(1)$ 。

一个只有一重循环的算法中原操作数执行次数与问题规模n的增长呈线性增大关系，记作 $O(n)$ ，也称线性阶。

其余常用的还有平方阶 $O(n^2)$ 、立方阶 $O(n^3)$ 、对数阶 $O(log_{2}n)$ 、指数阶 $O(2^n)$ 等，各种不同的时间复杂度存在着以下关系：

${\color{Red} O(1)<O(log_{2}n)<O(n)<O(nlog_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)}$

将 $O(log_{2}n),O(n),O(nlog_{2}n),O(n^2),O(n^3)$ 称为多项时间复杂度（polynomial time complexity），将 $O(2^n),O(n!)$ 等称为指数时间复杂度（exponential time complexity）。一个问题目前还可以用多项式时间复杂度的算法来求解，称为P问题；一个问题目前只能用指数时间复杂度的算法求解，称为NP问题。NP=P是否成立，也就是说，求解NP问题的指数时间复杂度算法能否转换成用多项式时间复杂度算法求解，这是目前计算机科学的难题之一。

（3）简化的算法时间复杂度分析

另外一种简化的算法时间复杂度分析方法仅仅考虑算法中的基本操作。所谓基本操作是指算法中最深层循环内的原操作。算法执行时间大致等于基本操作所需的时间*其运算次数。所以在算法分析中，计算 $T(n)$ 时仅仅考虑基本操作的运算次数。

对于【例1.6】，采用简化的时间复杂度分析方法，其中的基本操作是两重循环中最深层的语句3，分析它的频度，即 $T(n)=n^2=O(n^2)$ 。

从这两种方法得出算法的时间复杂度均为 $O(n^2)$ ，而后者的计算过程简单得多，所以后面主要采用简化的算法时间复杂度分析方法。

（4）时间复杂度的求和、求积定理

为了计算算法的时间复杂度，有以下两个定理：

求和定理：假设 $T_{1}(n),T_{2}(n)$ 是程序段 $P_{1},P_{2}$ 的执行时间，并且

$T_{1}(n)=O(f(n)),T_{2}(n)=O(g(n))$

那么先执行 $P_{1}$ ，再执行 $P_{2}$ 的总执行时间是 $T_{1},T_{2}=O(MAX(f(n),g(n)))$ 。例如多个并列循环就属于这种情况。

求积定理：假设 $T_{1}(n),T_{2}(n)$ 是程序段 $P_{1},P_{2}$ 的执行时间，并且

$T_{1}(n)=O(f(n)),T_{2}(n)=O(g(n))$

那么 $T_{1}*T_{2}=O(f(n)*g(n))$ ，例如多层嵌套就属于这种情况。

3.算法的最好、最坏和平均时间复杂度

设一个算法的输入规模是n， $D_{n}$ 是所有输入（实例）的集合，任意输入 $I\epsilon D_{n}$ ， $P(I)$ 是 $I$ 出现的频率，有 $\Sigma _{I\epsilon D_{n}}P(I)=1$ ， $T(I)$ 是算法在输入I下所执行的基本操作次数，则该算法的平均时间复杂度定义为

$E(n)=\sum_{I\epsilon D_{n} }P(I)*T(I)$

算法的最好时间复杂度是指算法在最好的情况下的时间复杂度，即

$B(n)=MIN_{I\epsilon D_{n}}\left \{ T(n) \right \}$

算法的最好情况和最坏情况分析是寻找该算法的极端实例，然后分析在该计算实例下算法的执行时间。

从中可以看出，计算平均时间复杂度时所需要考虑的所有情况，而计算最好和最坏时间复杂度时主要考虑一种或几种特殊情况。

4.递归算法时间复杂度

递归算法是指算法中出现自己调用自己的成分。递归算法分析不能前面简单的分析方法，递归算法分析也称为变长时空分析，非递归算法分析也成为定长时空分析。

在递归算法中首先写出对应的递推式，然后求解递推式得出算法的执行时间或者空间。下面通过一个示例讨论递归算法的时间分析方法。

三、算法空间性能分析

1.算法空间复杂度分析

一个算法的存储量包括输入数据所占的空间、程序本身所占的空间和临时变量所占的空间。这里在对算法进行存储空间分析时只考虑临时变量所占的空间，例如对于如【图1.1.6】所示的算法，其中临时变量为 $i,maxi$ 占用的空间。

所以，算法空间复杂度（space complexity）是对一个算法在运行过程中临时占用的存储空间大小的量度。一般也作为问题规模n的函数，以数量级形式给出，记作

$S(n)=O(g(n))$

其中。O的含义与时间复杂度中的含义相同。

若所需临时空间相对于问题规模来说是常数，则称此算法为原地工作算法或就地工作算法。

为什么算法占用的空间只需考虑临时空间，而不必考虑形参的空间呢？这是因为形参的空间会在调用该算法的算法中考虑，例如以下maxfun算法调用【图1.16】的max算法：

maxfun算法中为b数组分配了相应的内存空间，其空间复杂度为 $O(n)$ ，如果在max算法中再考虑形参a的空间，这样就重复计算了占用的空间。实际上在C/C++语言中，maxfun调用max时，max算法中形参a只是一个指向实参b数组的指针，即形参a只分配一个地址大小的空间，而非另外分配5个整形单元的空间。

【数据结构】CH1 绪论3——算法分析

前言

一、算法分析概述

二、算法时间性能分析

1.两种算法时间性能分析