算法效率的度量

AI 摘要

|

命题追踪 （算法题）分析时空复杂度（2010－2013、2015、2016、2018－2021）

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

时间复杂度

命题追踪 分析算法的时间复杂度（2011—2014、2017、2019、2022）

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为 $T(n)$ ，它是该算法问题规模 $n$ 的函数，时间复杂度主要分析 $T(n)$ 的数量级。算法中基本运算（最深层循环中的语句）的频度与 $T(n)$ 同数量级，因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。于是，算法的时间复杂度记为：$T(n)=O(f(n))$

式中，$O$ 的含义是 $T(n)$ 的数量级，其严格的数学定义是：若 $T(n)$ 和 $f(n)$ 是定义在正整数集合上的两个函数，则存在正常数 $C$ 和 $n_0$ ，使得当 $n⩾n_0$ 时，都满足 $0⩽T(n)⩽Cf(n)$ 。

算法的时间复杂度不仅依赖于问题的规模 $n$ ，也取决于待输入数据的性质（如输入数据元素的初始状态）。例如，在数组 $A[0\dots n-1]$ 中，查找给定值 $k$ 的算法大致如下：

i = n-1;
while ( i>=0 && (A[i]!=k) )
  i--;
return i;

该算法中语句 3 （基本运算）的频度不仅与问题规模 $n$ 有关，而且与下列因素有关：

（1）若 $A$ 中没有与 $k$ 相等的元素，则语句3 的频度 $f(n)=n$ 。

（2）若 $A$ 的最后一个元素等于 $k$ ，则语句3 的频度 $f(n)$ 是常数 0 。

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

平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。

在分析一个程序的时间复杂性时，有以下两条规则：

1）加法规则：$T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$

2）乘法规则：$T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$

例如，设 a{} 、 b{} 、 c{} 三个语句块的时间复杂度分别为 $O(1)、O(n)、O(n^2)$ ，则：

a {
  b{}
  c{}
}  //时间复杂度为O(n^2)，满足加法规则

a {
  b{
    c{ }
  }
}  //时间复杂度为O(n^3)，满足乘法规则

常见的渐近时间复杂度为： $O(1)<O({\log }_{2}n)<O(n)<O(n{\log }_{2}n)<O\left(n^2\right)<O\left(n^3\right)<O\left(2^n\right)<O(n!)<O\left(n^n\right)$

空间复杂度

算法的空间复杂度 $S(n)$ 定义为该算法所需的存储空间，它是问题规模 $n$ 的函数，记为 $S(n)=O(g(n))$

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。例如，若算法中新建了几个与输入数据规模 $n$ 相同的辅助数组，则空间复杂度为 $O(n)$ 。

算法原地工作是指算法所需的辅助空间为常量，即 $O(1)$ 。