一文搞懂算法时间复杂度
一、前言很多人觉得算法难，是因为被困在了时间和空间这两个维度上。如果不考虑时间和空间的因素，其实我们可以把所有问题都通过穷举解决，也就是你告诉计算机你要做什么，然后通过它强大的算力帮你计算。
今天，我就和大家来聊一下时间复杂度。
二、穷举
1、小试牛刀
[*]所谓穷举，也就是我们通常所说的枚举，就是把所有情况都遍历了的意思。举个最简单的例子：
【例1】给定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 个元素 a i a_i ai，求其中是偶数的数的个数。
[*]判断一个数是偶数还是奇数，只需要求它除上 2 的余数是 0 还是 1，那么我们把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，这里需要遍历所有的数，这就是穷举。如图二-1-1所示：
图二-1-1
[*]c++ 代码实现如下：
int countEven(int n, int a[]) {
int cnt = 0;
for(int i = 0; i < n; ++i) {
if(a % 2 == 0)
++cnt;
}
return cnt;
}
略带不屑的你
2、乘胜追击
[*]经过上面的例子，相信读者对穷举已经有一定的理解，那么我们来看看稍微复杂一点的情况。
【例2】给定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 个元素 a i a_i ai，求有多少个二元组 ( i , j ) (i,j) (i,j)，满足 a i + a j a_i + a_j ai+aj 是偶数 ( i < j ) (i \lt j) (i<j)。
[*]秉承穷举的思想，并且这里需要两个变量 i i i 和 j j j，所以可以枚举 a i a_i ai 和 a j a_j aj，再对 a i + a j a_i + a_j ai+aj 进行奇偶性判断，所以很快设计出一个利用穷举的算法。如图二-2-1所示：
图二-2-1
[*]c++ 代码实现如下：
int countEvenPair(int n, int a[]) {
int cnt = 0;
for(i = 0; i < n; ++i) {
for(j = i+1; j < n; ++j) {
if( (a + a) % 2 == 0)
++cnt;
}
}
return cnt;
}
若有所思的你
3、举一反三
[*]经过这两个例子，是不是对穷举已经有点感觉了？那么，我们继续来看下一个例子。
【例3】给定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 个元素 a i a_i ai，求有多少个三元组 ( i , j , k ) (i,j,k) (i,j,k)，满足 a i + a j + a k a_i + a_j + a_k ai+aj+ak 是偶数 ( i < j < k ) (i \lt j \lt k) (i<j<k)。
[*]给 10 秒倒计时，思考一下！
图二-3-1
[*]相信聪明的你也已经猜到了，直接给出代码：
int countEvenTriple(int n, int a[]) {
int cnt = 0;
for(i = 0; i < n; ++i) {
for(j = i+1; j < n; ++j) {
for(int k = j+1; k < n; ++k) {
if( (a + a + a) % 2 == 0)
++cnt;
}
}
}
return cnt;
}
[*]要求多少个元组，就是枚举多少层循环。
完全懂了的你
4、返璞归真
【例4】给定 n ( n ≤ 1000 ) n(n \le 1000) n(n≤1000) 个元素 a i a_i ai 和一个整数 k ( k ≤ n ) k (k \le n) k(k≤n)，求有多少个有序 k k k 元组，满足 它们的和 是偶数。
[*]一层循环，两层循环，三层循环， k k k 层循环？
[*]我们需要根据 k k k 的不同，决定写几层循环， k k k 的最大值为 1000，也就意味着我们要写 1000 的 i f e l s e if \ else if else。
[*]显然，这样是无法接受，比较暴力的做法是采用到递归，c++ 代码实现如下：
int dfs(int n, int a[], int start, int k, int sum) {
if(k == 0)
return sum % 2 ? 0 : 1; // (1)
int s = 0;
for(int i = start; i < n; ++i)
s += dfs(n, a, i+1, k-1, sum + a); // (2)
return s;
}
"啊这…" 的你
[*]1）dfs(int n, int a[], int start, int k, int sum)这个函数的含义是：给定 n n n 元素的数组 a [ ] a[] a[]，从下标 s t a r t start start 开始，选择 k k k 个元素，得到的和为 s u m sum sum 的情况下的方案数，当 k = 0 k=0 k=0 时代表的是递归的出口；
[*]2）当前第 i i i 元素选择以后，剩下就是从 i + 1 i+1 i+1 个元素开始选择 k − 1 k-1 k−1 个的情况，递归求解。
[*]我们简单分析一下， n n n 个元素选择 k k k 个，根据排列组合，方案数为： C n k C_n^k Cnk，当 n = 1000 ， k = 500 n=1000，k=500 n=1000，k=500 时已经是天文数字，这段代码是完全出不了解的。
当然，对于初学者来说，这段代码如果不理解，问题也不大，只是为了说明穷举这个思想。
充满求知欲的你
三、时间复杂度
1、时间复杂度的表示法
1、时间函数
[*]时间复杂度往往会联系到一个函数，自变量表示规模，应变量表示执行时间。
[*]这里所说的执行时间，是指广义的时间，也就是单位并不是 “秒”、“毫秒” 这些时间单位，它代表的是一个 “执行次数” 的概念。我们用 f ( n ) f(n) f(n) 来表示这个时间函数。
2、经典函数举例
[*]在【例1】中，我们接触到了单层循环，这里的 n n n 是一个变量，随着 n n n 的增大，执行次数增大，执行时间就会增加，所以就有了时间函数的表示法如下：
[*]f ( n ) = n f(n) = n f(n)=n
图三-2-1
[*]这个就是最经典的线性时间函数。
[*]在【例2】中，我们接触到了双层循环，它的时间函数表示法如下：
[*]f ( n ) = n ( n − 1 ) 2 f(n) = \frac {n(n-1)} 2 f(n)=2n(n−1)
图三-2-2
[*]这是一个平方级别的时间函数。
[*]在【例3】中，我们接触到了三层循环，它的时间函数表示法如下：
[*]f ( n ) = n ( n − 1 ) ( n − 2 ) 6 f(n) = \frac {n(n-1)(n-2)} 6 f(n)=6n(n−1)(n−2)
图三-2-3
[*]这是一个立方级别的时间函数。
3、时间复杂度
[*]一个算法中的语句执行次数称为语句频度或时间频度。记为 T ( n ) T(n) T(n)。
[*]并且我们有一个更加优雅的表示法，即：
[*]T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))
[*]其中 O O O 念成 “大O”；
[*]1）当 f ( n ) = n f(n) = n f(n)=n，我们称这个算法拥有线性时间复杂度，记作 O ( n ) O(n) O(n)；
[*]2）当 f ( n ) = n ( n − 1 ) 2 f(n) = \frac {n(n-1)} 2 f(n)=2n(n−1)，我们称这个算法拥有平方级时间复杂度，记作 O ( n 2 ) O(n^2) O(n2)；
[*]3）当 f ( n ) = n ( n − 1 ) ( n − 2 ) 6 f(n) = \frac {n(n-1)(n-2)} 6 f(n)=6n(n−1)(n−2), 我们称这个算法拥有立方级的时间复杂度，记作 O ( n 3 ) O(n^3) O(n3)；
[*]这时候我们发现， f f f 的函数可能很复杂，但是 O O O 表示的函数往往比较简单，它舍弃了一些 “细节” ，这是为什么呢？
[*]接下来我们来谈下数学上一个非常有名的概念 “高阶无穷小”。
4、小巫见大巫
[*]有这么一个定义：如果 l i m ( β / α ) = 0 lim(β / α) = 0 lim(β/α)=0，则称“ β β β 是比 α α α 较高阶的无穷小”。
图三-4-1
[*]如果对极限没有概念，那就让我用更加通俗的语言来解释一下。
[*]我们来看上面提到的一个函数：
[*]f ( n ) = n ( n − 1 ) 2 = 1 2 n 2 − 1 2 n f(n) = \frac {n(n-1)} 2 = \frac 1 2 n^2 - \frac 1 2 n f(n)=2n(n−1)=21n2−21n
[*]总共两部分组成：一部分是 n 2 n^2 n2 的部分，另一部分是 n n n 的部分，直观感受，那个更大？
[*]显而易见，一定是 n 2 n^2 n2，相对于 n 2 n^2 n2 来说， n n n 就是 “小巫见大巫” ！
[*]所以随着 n n n 的增长，线性的部分增长已经跟不上平方部分，这样，线性部分的时间消耗相对于平方不分来说已经 “微不足道”，所以我们就索性不提它了，于是就有时间复杂度表示如下：
[*]T ( n ) = O ( f ( n ) ) = O ( 1 2 n 2 − 1 2 n ) = O ( 1 2 n 2 ) = O ( n 2 ) \begin{aligned} T(n) &= O(f(n)) \\ &= O(\frac 1 2 n^2 - \frac 1 2 n) \\ &= O(\frac 1 2 n^2) \\ &= O(n^2)\end{aligned} T(n)=O(f(n))=O(21n2−21n)=O(21n2)=O(n2)
5、简化系数
[*]我们发现上述的公式推导的过程中，将 n 2 n^2 n2 前面的 1 2 \frac 1 2 21 给去掉了，道理也是一样，时间复杂度描述的更多的是一个数量级，所以尽量减少干扰项。对于两个不同的问题，可能执行时间不同，但是我们可以说他们的时间复杂度是一样的。
[*]接下来让我们来看下一些常见的时间复杂度。
四、常见的时间复杂度
1、常数时间
const int MAXN = 1024;
int getMAXN() {
return MAXN;
}
[*]这个比较好理解，一共就一句话，没有循环，是常数时间，表示为 O ( 1 ) O(1) O(1)。
2、对数时间
【例4】给定 n ( n ≤ 100000 ) n(n \le 100000) n(n≤100000) 个元素的有序数组 a i a_i ai 和 整数 v v v，求 v v v 在数组中的下标，不存在输出 -1。
[*]这个问题就是一个常见的查询问题，我们可以用 O ( n ) O(n) O(n) 的算法遍历整个数组，然后去找 v v v 的值。
[*]当然，也有更快的办法，注意到题目中的条件，数组 a i a_i ai 是有序的，所以我们可以利用二分查找来实现。
int binaryFind(int n, int a[], int v) {
int l = 0, r = n - 1;
while(l <= r) {
mid = (l + r) >> 1;
if(a == v) return mid;
if(a < v) {
r = mid + 1;
}else {
l = mid + 1;
}
}
return -1;
}
[*]这是一个二分查找的实现，时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n)。
[*]每次相当于把 n n n 切半，即：
[*]n → n 2 → n 4 → . . . → n 2 k → . . . → 0 n \to \frac n 2 \to \frac n 4 \to ...\to \frac n {2^k} \to ... \to 0 n→2n→4n→...→2kn→...→0
[*]这条路径的长度也就是执行次数，也就是要求 2 k ≤ n 2^k \le n 2k≤n 中的 k k k 的最大值，两边取以2为底的对数，得到：
[*]k ≤ l o g 2 n k \le log_2n k≤log2n
[*]所以 T ( n ) = O ( f ( n ) ) = O ( k ) = O ( l o g 2 n ) T(n) = O(f(n)) = O(k) = O(log_2n) T(n)=O(f(n))=O(k)=O(log2n)。
[*]（图上一个）
3、根号时间
【例5】给定一个数 n ( n ≤ 1 0 9 ) n(n \le 10^9) n(n≤109)，问 n n n 是否是一个素数（素数的概念，就是除了1和它本身，没有其它因子）。
[*]基于素数的概念，我们可以枚举所有 i ∈ [ 2 , n ) i \in [2, n) i∈[2,n)，看能否整除 n n n，一旦能整除，代表找到了一个因子，则不是素数；当所有数枚举完还没找到，它就是素数。
[*]但是这样做，显然效率太低，所以我们需要进行一些思考，最后得到以下算法：
bool isPrime(int n) {
int i;
int sqrtn = sqrt(n + 0.0);
for(int i = 2; i <= sqrtn; ++i) {
if(n % i == 0) {
return false;
}
}
return true;
}
[*]这个算法的时间复杂度为 O ( n ) O(\sqrt n) O(n )。
[*]为什么只需要枚举 n \sqrt n n 内的数呢？
[*]因为一旦有一个因子 s s s，必然有另一个因子 n s \frac n s sn，它们之间必然有个大小关系，无论是 s ≤ n s s \le \frac n s s≤sn 还是 n s ≤ s \frac n s \le s sn≤s，都能通过两边乘上 s s s 得出：
[*]s ≤ n s \le \sqrt n s≤n
4、线性时间
[*]这个就不用多说了，【例1】的实现就是线性时间，即 O ( n ) O(n) O(n)。
4、线性对数时间
【例6】给定 n ( n ≤ 100000 ) n(n \le 100000) n(n≤100000) 个元素 a i a_i ai，求满足 a i + a j = 1024 a_i + a_j = 1024 ai+aj=1024 的有序二元组 ( i , j ) (i,j) (i,j) 有多少对。
[*]首先，还是先思考最朴素的算法，当然是两层枚举了，参考【例2】，时间复杂度 O ( n 2 ) O(n^2) O(n2)。
[*]但是，这个问题 n n n 的范围较大。
[*]我们来看下这个问题，如果你对 【例4】已经理解了，那么这个问题也就不难了。
[*]我们可以先对所有元素 a i a_i ai 按照递增排序，然后枚举 a i a_i ai，并且在 [ i + 1 , n ) [i+1, n) [i+1,n) 范围内找是否存在 a j = 1024 − a i a_j = 1024 - a_i aj=1024−ai，存在则计数器 + 1，而这个找的过程可以采用二分枚举。所以时间复杂度就是： O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)。
5、多项式时间
[*]多项式的含义是函数 f ( n ) f(n) f(n) 可以表示成如下形式：
[*]f ( n ) = a n k + b n k − 1 + . . . + C f(n) = an^k + bn^{k-1} + ... + C f(n)=ank+bnk−1+...+C
[*]所以 O ( n 5 ) O(n^5) O(n5)、 O ( n 4 ) O(n^4) O(n4)、 O ( n 3 ) O(n^3) O(n3)、 O ( n 2 ) O(n^2) O(n2)、 O ( n ) O(n) O(n) 都是多项式时间。
6、指数时间
【例7】给出 n ( n ≤ 15 ) n(n \le 15) n(n≤15) 个点，以及每两个点之间的关系（连通还是不连通），求一个最大的集合，使得在这个集合中都连通。
[*]这是求子集的问题，由于最多只有 15 15 15 个点，我们就可以枚举每个点选或者不选，总共 2 n 2^n 2n 种情况，然后再判断是否满足题目中的连通性，这个算法时间复杂度为 O ( n 2 2 n ) O(n^22^n) O(n22n)；
[*]当然有更加优秀的算法，但不是本文讨论的重点，所以就交给优秀的你自己去探索啦！
7、阶乘时间
【例8】给定 n ( n ≤ 10 ) n(n \le 10) n(n≤10) 个点，并且给出任意两点间的距离，求从 s s s 点开始经过所有点回到 s s s 的距离的最小值。
[*]这个问题就是典型的暴力枚举所有情况求解，可以把这些点当成是一个排列，所以排列方案数为 n ! n! n!。
[*]暴力枚举的时间复杂度为 O ( n ! ) O(n!) O(n!)。
[*]当然，一般这类问题，暴力搜索没有实际意义，我们可以通过动态规划来进行优化。
五、如何判断时间复杂度
[*]接下来我们来讨论下，如何通过一个问题的规模来判断这个问题应该能够承受的时间复杂度。
1、标准
[*]首先，我们需要一个标准，也就是总执行次数多少合适。
[*]这个标准是我经过多年做题经验得出，我们把它定义为 S = 1 0 6 S = 10^6 S=106。
2、问题规模
[*]有了标准以后，我们还需要知道问题规模，也就是 O ( n ) O(n) O(n) 中的 n n n。
3、套公式
[*]然后就是凭感觉套公式了。
[*]当 n < 12 n < 12 n<12 时，可能是需要用到阶乘级别的算法，即 O ( n ! ) O(n!) O(n!)；
[*]当 n < 16 n < 16 n<16 时，可能是需要状态压缩的算法，比如 O ( 2 n ) O(2^n) O(2n)、 O ( n 2 n ) O(n2^n) O(n2n)、 O ( n 2 2 n ) O(n^22^n) O(n22n)；
[*]当 n < 30 n < 30 n<30 时，可能是需要 O ( n 4 ) O(n^4) O(n4) 的算法，因为 3 0 4 30^4 304 差不多接近 1 0 6 10^6 106；
[*]当 n < 100 n < 100 n<100 时，可能是需要 O ( n 3 ) O(n^3) O(n3) 的算法，因为 10 0 3 = 1 0 6 100^3 = 10^6 1003=106；
[*]当 n < 1000 n < 1000 n<1000 时，可能是需要 O ( n 2 ) O(n^2) O(n2) 的算法，因为 100 0 2 = 1 0 6 1000^2 = 10^6 10002=106；
[*]当 n < 100000 n < 100000 n<100000 时，可能是需要 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)、 O ( n ( l o g 2 n ) 2 ) O(n(log_2n)^2) O(n(log2n)2) 的算法；
[*]当 n < 1000000 n < 1000000 n<1000000 时，可能是需要 O ( n ) O(\sqrt n) O(n )、 O ( n ) O(n) O(n) 的算法；
[*]细心的读者可能会发现，我在描述的时候都是用了可能的语气，那是因为以上数据量都是我通过做题总结出来的，有时候还需要结合题目本身的时间限制、出题人的阴险程度 来决定，所以不能一概而论。
页:
[1]