Time Complexity - 时间复杂度

简介

狭义的说，算法是利用计算机软件解决数学问题的方法。对于具有确定数学模型的问题，将问题数据输入算法中就可以得到该问题的解。简单的问题比如求两个位于$[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）](https://linrongbin16.gitbook.io/gitbook-way-to-algorithm/search/binarysearch)； (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