TimeComplexity 时间复杂度

简介

狭义的说，算法是利用计算机软件解决数学问题的方法。对于具有确定数学模型的问题，将问题数据输入算法中就可以得到该问题的解。简单的问题比如求两个位于$[1000000000, -1000000000]$之间的整数之和，这个问题的输入数据是两个整数$a$和$b$，解是整数$c$，其中$c = a + b$。复杂的问题比如求拥有$n$个节点网络流的最大流，输入数据是一个网络流$G = <V, E>$，解是该网络流的最大流$F_{max}$。

时间复杂度是衡量算法性能的度量。如果把算法比作数学中的函数，那么时间复杂度就是运行该函数所消耗的时间、空间（内存）。一般将简单的数学计算、读写变量看作基本操作，其消耗的时间看作基本时间单位。基本操作只是一种抽象的认知，并不是死板规定。比如在计算两个32位整数$a \times b$的问题上，考虑下面两种算法：

(1) 累加模拟法：重复$a$个$b$累加，或$b$个$a$累加。该算法把一次相加看作一个基本操作，则其所需时间至多为$max(a, b)$个时间单位；

(2) Booth’s Multiplication Algorithm：利用位操作计算两整数相乘。假设$a = b = 10000$，那么第$(1)$种算法需要$10000$次累加操作，而该算法只需要$5^2 = 25$次位操作，而且CPU的位操作速度极快，一次位操作所需的真正时间远小于一次整数加法操作；

在上面两种算法中，认为加法操作是第$(1)$个算法中的基本操作，位操作是第$(2)$个算法中的基本操作。虽然实际的x86或amd64架构CPU上加法操作和位操作的性能相差甚远，但在算法中都抽象的认为它们都是基本操作，忽略其细节的差别。我们更关注第$(2)$个算法通过利用整数$a = b = 10000$的比特位为$5$，远小于整数本身$10000$，从而将运算次数从$10000$次降低到了$5^2$次带来的提高。

渐进记号

不同问题的数据规模是不一样的，求两整数之和的问题规模是两个整数，即$2$；求拥有$n$个节点的网络流的最大流的问题规模则是$n$。常用渐进记号$T$表示一个问题的规模，比如$T(1)$表示问题规模是常数的，$T(n)$表示问题规模是线性的。

不同算法消耗的时间、空间也不一样，用渐进记号$O$来描述算法的时间复杂度或空间复杂度。常见的时间复杂度有：

(1) 常数时间：$O(1)$，不论问题规模，算法都能在一个固定时间内解决问题，这里的$1$并非特指1次操作，而是指常数数量操作，因此也不存在$O(2), O(10)$这样的复杂度。比如上文中的两整数相加；

(2) 对数时间：$O(log_2 n)$、$O(n \cdot log_2 n)，对于数据规模为$ n $$的问题，可以在对数时间内解决。比如二分搜索（Binary Search）；

(3) 线性时间：$O(n)$，对于数据规模为$n$的问题，解决时间随着数据规模的增长呈线性增长；

(4) 二次方时间：$O(n^2)$，对于数据规模为$n$的问题，需要在次方级别的时间解决。比如图论中遍历一个拥有$n$个节点完全图的所有边，需要嵌套的内外两层循环来遍历图中的所有节点，外层遍历图中的每个节点，内层对于每个节点又需要遍历图中的其他所有节点；

(5) 三次方时间$O(n^3)$、阶乘时间$O(n!)$等等；

算法复杂度的关键在于计算模型所消耗的操作数量，随着问题规模增长的膨胀程度。当问题规模$n$足够大时有：

$$O(n^3) \gt O(n^2) \gt O(n \cdot log_2 n) \gt O(n) \gt O(log_2 n) \gt O(1)$$

渐近记号给出了一个函数的上界和下界。

复杂度

判定一个算法的时间复杂度或空间复杂度需要一定的推导过程（非常熟悉的也可以一眼看出来）。

算法步骤可以转化为等式，等式左右两边分别是计算后和计算前的问题规模。转化等式遵循以下几个原则：

(1) 用常数复杂度$O(1)$代替运算中的所有基本操作。比如$z = a + b \times c \div (2 * d + e)$的复杂度为$O(1)$；

(2) 在函数中只保留最高阶运算，删除低阶运算。比如$n^2 + log_2 n + 3 \times 4$的复杂度为$O(n^2) + O(log_2 n) + O(1)$，删除低阶运算后复杂度为$O(n^2)$；

(3) 如果运算的复杂度高于$O(1)$，则将周围的常数乘数去掉。比如$2 \cdot n$的复杂度为$O(2 \cdot n)$，将常数乘数去掉后复杂度为$O(n)$；

下面我们对几个算法的时间复杂度进行推导：

(1) 两整数相加$c = a + b$

$$T(1) = T(1) + T(1) = O(1)$$

上式中，等号左边是计算后的结果，其规模为$T(1)$（结果为一个整数）；等号右边是计算前的问题规模，加法操作的时间复杂度为$O(1)$，因此该算法的时间复杂度为$O(1)$。

(2) 对拥有$n$个互不相等的整数的数组进行快速排序

$$T(n) = \begin{cases} 1 & n = 1 \\ 2 \cdot T(\frac{n}{2}) + O(n) & n \gt 1 \end{cases}$$

快速排序的每次递归中，首先需要选取一个元素作为哨兵，然后遍历所有元素，将小于哨兵的元素移动到其左边，将大于哨兵的元素移动到其右边，该遍历操作的时间复杂度为$O(n)$。之后对于哨兵左右两边的子数组，递归的进行下一轮移动操作。因此可以得到上式，等号左边是本次操作前的问题规模$T(n)$，等号右边是本次操作后还需要解决的问题规模，即2个$T(\frac{n}{2})$，而本次操作所需要的操作代价为$O(n)$。

对该递归式推导可得：

$$\begin{matrix} T(n) & = & 2 \cdot T(\frac{n}{2}) + n & & \\ & = & 2 \cdot T(2 \cdot T(\frac{n}{2^2}) + \frac{n}{2}) + n & = & 2^2 \cdot T(\frac{n}{2^2}) + 2 \cdot n \\ & = & 2 \cdot T(2 \cdot T(\frac{n}{2^3}) + \frac{n}{2^2}) + 2 \cdot n & = & 2^3 \cdot T(\frac{n}{2^3}) + 3 \cdot n \\ & = & \cdots & & \end{matrix}$$

假设递归层数为$L$，可得：

$$T(\frac{n}{2^L}) = 1$$

因为：

$$\frac{n}{2^L} = 1$$

可以得到：

$$L = log_2 n$$

因此递归式可推导为：

$$\begin{matrix} T(n) & = & 2^L \cdot T(\frac{n}{2^L}) + L \cdot n \\ & = & 2^{log_2 n} + n \cdot log_2 n \\ & = & n + n \cdot log_2 n \\ & = & O(n \cdot log_2 n) \end{matrix}$$

最终可以得到快速排序的时间复杂度为$O(n \cdot log_2 n)$。

Introduction to Algorithms

• I.Foundations - 2.Getting Started - 2.3.Designing algorithms