大家好，又见面了，我是你们的朋友全栈君。

一、前言

  目前本专栏正在进行优惠活动，在博主主页添加博主好友（好友位没有满的话），可以获取 付费专栏优惠券。
  「数据结构」 和 「算法」 是密不可分的，两者往往是相辅相成的，所以，在学习 「数据结构」 的过程中，不免会遇到各种「算法」。
  零基础学算法的最好方法，莫过于刷题了。当然，刷题是不够的，刷的过程中也要多多总结，多多思考，养成 「经常思考」 的习惯，这就是所谓的 「 流水不腐，户枢不蠹 」，任何事情都是需要坚持的，刷题也一样，没有刷够足够的题，就很难做出系统性的总结。所以上大学的时候，我花了三年的时间来刷题， 工作以后还是会抽点时间出来刷题。
  千万不要用工作忙来找借口，时间挤一挤总是有的。
  很多人觉得算法难，是因为被困在了时间和空间这两个维度上。如果不考虑时间和空间的因素，其实我们可以把所有问题都通过「穷举法」 来解决，也就是你告诉计算机你要做什么，然后通过它强大的算力帮你计算。
  那么，说到了时间，今天我就和大家来聊一下

「 算法时间复杂度 」

 

二、穷举法

1、单层循环

• 所谓穷举法，就是我们通常所说的枚举，就是把所有情况都遍历了（跑到）的意思。举个最简单的例子：

【例题1】给定 $n(n\le 1000)$ 个元素 $a_i$，求其中 奇数 有多少个。

• 判断一个数是偶数还是奇数，只需要求它除上 2 的余数是 0 还是 1，那么我们把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，这里需要遍历所有的数，这就是穷举。如图二-1-1所示：
  
  
  图二-1-1
  
• c/c++ 代码实现如下：

int countOdd(int n, int a[]) { 
   
    int cnt = 0;
    for(int i = 0; i < n; ++i) { 
   
        if(a[i] & 1)
            ++cnt;
    }
    return cnt;
}

• 其中a & 1等价于a % 2，代码a模 2 的余数；
• 具体原因可以参见位与运算符的用法：☀️光天化日学C语言☀️（14）- 位运算 & 的应用。

2、双层循环

• 经过上面的例子，相信你对穷举法已经有一定的理解，那么我们来看看稍微复杂一点的情况。

【例题2】给定 $n(n\le 1000)$ 个元素 $a_i$，求有多少个二元组$(i,j)$，满足 $a_i+a_j$ 是奇数 $(i<j)$。

• 我们还是秉承穷举法的思想，这里需要两个变量 $i$ 和 $j$，所以可以枚举 $a_i$ 和 $a_j$，再对 $a_i+a_j$ 进行奇偶性判断，所以很快设计出一个利用穷举的算法。如图二-2-1所示：
  
  
  图二-2-1
  
• c/c++ 代码实现如下：

int countOddPair(int n, int a[]) { 
   
    int cnt = 0;
    for(i = 0; i < n; ++i) { 
   
        for(j = i+1; j < n; ++j) { 
   
            if( (a[i] + a[j]) & 1)
                ++cnt;
        }
    }
    return cnt;
}

3、三层循环

• 经过这两个例子，是不是对穷举已经有点感觉了？那么，我们继续来看下一个例子。

【例题3】给定 $n(n\le 1000)$ 个元素 $a_i$，求有多少个三元组$(i,j,k)$，满足 $a_i+a_j+a_k$ 是奇数 $(i<j<k)$。

• 相信聪明的你也已经猜到了，直接给出代码：

int countOddTriple(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[i] + a[j] + a[k]) & 1 )
                    ++cnt;
            }
        }
    }
    return cnt;
}

• 这时候，相信聪明的你，已经意识到一个问题；
• 它就是：
  
• 是的，随着循环嵌套的增多，时间消耗会越来越多，并且是三个循环是乘法的关系，也就是遍历次数随着 $n$ 的增加，呈立方式的增长。

4、递归枚举

  【例题4】给定 $n(n\le 1000)$ 个元素 $a_i$ 和一个整数 $k(k\le n)$，求有多少个有序 $k$ 元组，满足 它们的和 是偶数。

• 一层循环，两层循环，三层循环，$k$ 层循环？
• 我们需要根据 $k$ 的不同，决定写几层循环，$k$ 的最大值为 1000，也就意味着我们要写 1000 的 if else 语句。
• 显然，这样是无法接受，比较暴力的做法是采用到递归；
• c/c++ 代码实现如下：

int dfs(int n, int a[], int start, int k, int sum) { 
   
    if(k == 0)
        return (sum & 1) ? 0 : 1;             // (1)
    int s = 0; 
    for(int i = start; i < n; ++i)
        s += dfs(n, a, i+1, k-1, sum + a[i]); // (2)
    return s;
}

• 这是一个经典的深度优先遍历的过程，对于初学者来说可能比较难理解，这个过程比较复杂，我来简单解释一下。
  

• $(1)$ dfs(int n, int a[], int start, int k, int sum)这个函数的含义是：给定 $n$ 元素的数组 $a[]$，从下标 $start$ 开始，选择 $k$ 个元素，得到的和为 $sum$ 的情况下的方案数，当 $k=0$ 时代表的是递归的出口；

• $(2)$ 当前第 $i$ 元素选择以后，剩下就是从 $i+1$ 个元素开始选择 $k-1$ 个的情况，递归求解。

• 我们简单分析一下，$n$ 个元素选择 $k$ 个，根据排列组合，方案数为：$C_n^k$，当 $n=1000，k=500$ 时已经是天文数字，这段代码是完全出不了解的。

• 当然，对于初学者来说，这段代码如果不理解，问题也不大，只是为了说明穷举这个思想。

三、时间复杂度

1、时间复杂度的表示法

  在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随着 $n$ 的变化情况而确定 $T(n)$ 的数量级。
  算法的时间复杂度，就是算法的时间度量，记作：$$T(n)=O(f(n))$$ 用大写的 O 来体现算法时间复杂度的记法，我们称之为 大 O 记法。

1、时间函数

时间复杂度往往会联系到一个函数，自变量 表示规模，应变量 表示执行时间。

• 这里所说的执行时间，是指广义的时间，也就是单位并不是 “秒”、“毫秒” 这些时间单位，它代表的是一个 “执行次数” 的概念。我们用 $f(n)$ 来表示这个时间函数。

2、经典函数举例

• 在【例题1】中，我们接触到了单层循环，这里的 $n$ 是一个变量，随着 $n$ 的增大，执行次数增大，执行时间就会增加，所以就有了时间函数的表示法如下：
• $$f(n)=n$$
  
  
  图三-2-1
  
• 这个就是最经典的线性时间函数。
• 在【例题2】中，我们接触到了双层循环，它的时间函数表示法如下：
• $$f(n)=\frac{n(n-1)}{2}$$
  
  
  图三-2-2
  
• 这是一个平方级别的时间函数。
• 在【例3】中，我们接触到了三层循环，它的时间函数表示法如下：
• $$f(n)=\frac{n(n-1)(n-2)}{6}$$
  
  
  图三-2-3
  
• 这是一个立方级别的时间函数。

3、时间复杂度

• 一个算法中的语句执行次数称为语句频度或时间频度。记为 $T(n)$。
• 并且我们有一个更加优雅的表示法，即：
• $$T(n)=O(f(n))$$
• 其中 $O$ 念成 “大O”；
• 1）当 $f(n)=n$，我们称这个算法拥有线性时间复杂度，记作 $O(n)$；
• 2）当 $f(n)=\frac{n(n-1)}{2}$，我们称这个算法拥有平方级时间复杂度，记作 $O(n^2)$；
• 3）当 $f(n)=\frac{n(n-1)(n-2)}{6}$, 我们称这个算法拥有立方级的时间复杂度，记作 $O(n^3)$；
• 这时候我们发现，$f$ 的函数可能很复杂，但是 $O$ 表示的函数往往比较简单，它舍弃了一些 “细节” ，这是为什么呢？
• 接下来我们来谈下数学上一个非常有名的概念 “高阶无穷小”。

4、高阶无穷小

• 有这么一个定义：如果 $lim(\beta /\alpha )=0$，则称“ $\beta$ 是比 $\alpha$ 较高阶的无穷小”。

• 如果对极限没有什么概念，我会用更加通俗的语言来解释一下。

• 我们来看上面提到的一个函数：

• $$f(n)=\frac{n(n-1)}{2}=\frac{1}{2}{n}^2-\frac{1}{2}n$$

• 总共两部分组成：一部分是 $n^2$ 的部分，另一部分是 $n$ 的部分，直观感受，那个更大呢？
  

• 显而易见，一定是 $n^2$，相对于 $n^2$ 来说， $n$ 就是 “小巫见大巫” ！

• 所以随着 $n$ 的增长，线性的部分增长已经跟不上平方部分，这样，线性部分的时间消耗相对于平方不分来说已经 “微不足道”，所以我们就索性不提它了，于是就有时间复杂度表示如下：

• $$\begin{array}{rl}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{array}$$

• 所以它的时间复杂度就是 $O(n^2)$ 了。

5、简化系数

• 我们发现上述的公式推导的过程中，将 $n^2$ 前面的系数 $\frac{1}{2}$ 给去掉了，这是由于 时间复杂度描述的更多的是一个数量级，所以尽量减少干扰项。对于两个不同的问题，可能执行时间不同，但是我们可以说他们的 时间复杂度 是一样的。
• 接下来让我们来看下一些常见的时间复杂度。

四、常见的时间复杂度

1、常数阶

const int MAXN = 1024;
int getMAXN() { 
   
	return MAXN;
}

• 这个比较好理解，一共就一句话，没有循环，是常数时间，表示为 $O(1)$。

2、对数阶

【例题4】给定 $n(n\le 100000)$ 个元素的有序数组 $a_i$ 和 整数 $v$，求 $v$ 在数组中的下标，不存在输出 -1。

• 这个问题就是一个常见的查询问题，我们可以用 $O(n)$ 的算法遍历整个数组，然后去找 $v$ 的值。
• 当然，也有更快的办法，注意到题目中的条件，数组 $a_i$ 是有序的，所以我们可以利用二分查找来实现。

int bin(int n, int a[], int v) { 
   
	int l = 0, r = n - 1;
	while(l <= r) { 
   
		mid = (l + r) >> 1;
		if(a[mid] == v) 
		    return mid;
		else if(a[mid] < v)
			r = mid + 1;
		else
			l = mid + 1;
	}
	return -1;
}

• 这是一个二分查找的实现，时间复杂度为 $O(lo{g}_{2}n)$。
• 每次相当于把 $n$ 切半，即：
• $$n\to \frac{n}{2}\to \frac{n}{4}\to ...\to \frac{n}{2^k}\to ...\to 0$$
• 这条路径的长度也就是执行次数，也就是要求 $2^k\le n$ 中的 $k$ 的最大值，两边取以2为底的对数，得到：
• $$k\le lo{g}_{2}n$$
• 所以 $T(n)=O(f(n))=O(k)=O(lo{g}_{2}n)$。

3、根号阶

【例题5】给定一个数 $n(n\le 10^9)$，问 $n$ 是否是一个素数（素数的概念，就是除了1和它本身，没有其它因子）。

• 基于素数的概念，我们可以枚举所有 $i\in [2,n)$，看能否整除 $n$，一旦能整除，代表找到了一个因子，则不是素数；当所有数枚举完还没找到，它就是素数。
• 但是这样做，显然效率太低，所以我们需要进行一些思考，最后得到以下算法：

bool isPrime(int n) { 
   
    int i;
    if(n == 1) { 
   
        return false;
    }
    int sqrtn = sqrt(n + 0.0);
    for(int i = 2; i <= sqrtn; ++i) { 
   
        if(n % i == 0) { 
   
            return false;
        }
    }
    return true;
}

• 这个算法的时间复杂度为 $O(\sqrt{n})$。
• 为什么只需要枚举 $\sqrt{n}$ 内的数呢？
• 因为一旦有一个因子 $s$，必然有另一个因子 $\frac{n}{s}$，它们之间必然有个大小关系，无论是 $s\le \frac{n}{s}$ 还是 $\frac{n}{s}\le s$，都能通过两边乘上 $s$ 得出：
• $$s\le \sqrt{n}$$

4、线性阶

• 【例题1】中我们接触到的单层循环，这里的 $n$ 是一个变量，随着 $n$ 的增大，执行次数增大，执行时间就会增加，所以就有了时间函数的表示法如下：
• $$f(n)=n$$
  
• 这个就是最经典的线性时间，即 $O(n)$。

5、线性对数阶

【例题6】给定 $n(n\le 100000)$ 个元素 $a_i$，求满足 $a_i+a_j=1024$ 的有序二元组 $(i,j)$ 有多少对。

• 首先，还是先思考最朴素的算法，当然是两层枚举了，参考【例题2】，时间复杂度 $O(n^2)$。
• 但是，这个问题 $n$ 的范围较大。
• 我们来看下这个问题，如果你对 【例题4】已经理解了，那么这个问题也就不难了。
• 我们可以先对所有元素 $a_i$ 按照递增排序，然后枚举 $a_i$，并且在 $[i+1,n)$ 范围内找是否存在 $a_j=1024-a_i$，存在则计数器 + 1，而这个找的过程可以采用二分枚举。所以时间复杂度就是： $O(nlo{g}_{2}n)$。

6、多项式阶

• 多项式的含义是函数 $f(n)$ 可以表示成如下形式：
• $$f(n)=a{n}^k+b{n}^{k-1}+...+C$$
• 所以 $O(n^5)$、$O(n^4)$、$O(n^3)$（立方阶）、$O(n^2)$（平方阶）、$O(n)$（线性阶） 都是多项式时间。

7、指数阶

【例题7】给出 $n(n\le 15)$ 个点，以及每两个点之间的关系（连通还是不连通），求一个最大的集合，使得在这个集合中都连通。

• 这是求子集的问题，由于最多只有 $15$ 个点，我们就可以枚举每个点选或者不选，总共 $2^n$ 种情况，然后再判断是否满足题目中的连通性，这个算法时间复杂度为 $O(n^2{2}^n)$；
• 当然有更加优秀的算法，但不是本文讨论的重点，所以就交给优秀的你自己去探索啦！

8、阶乘阶

【例题8】给定 $n(n\le 12)$ 个点，并且给出任意两点间的距离，求从 $s$ 点开始经过所有点回到 $s$ 的距离的最小值。

• 这个问题就是典型的暴力枚举所有情况求解，可以把这些点当成是一个排列，所以排列方案数为 $n!$。
• 暴力枚举的时间复杂度为 $O(n!)$。
• 当然，一般这类问题，暴力搜索没有实际意义，我们可以通过动态规划来进行优化。

五、如何判断时间复杂度

• 接下来我们来讨论下，如何通过一个问题的规模来判断这个问题应该能够承受的时间复杂度。

1、标准

• 首先，我们需要一个标准，也就是总执行次数多少合适。
• 这个标准是我经过多年做题经验得出，我们把它定义为 $S=10^6$。

2、问题规模

• 有了标准以后，我们还需要知道问题规模，也就是 $O(n)$ 中的 $n$。

3、套公式

• 然后就是凭感觉套公式了。
• 当 $n<12$ 时，可能是需要用到阶乘级别的算法，即 $O(n!)$；
• 当 $n<16$ 时，可能是需要状态压缩的算法，比如 $O(2^n)$、$O(n{2}^n)$、$O(n^2{2}^n)$；
• 当 $n<30$ 时，可能是需要 $O(n^4)$ 的算法，因为 $30^4$ 差不多接近 $10^6$；
• 当 $n<100$ 时，可能是需要 $O(n^3)$ 的算法，因为 $100^3=10^6$；
• 当 $n<1000$ 时，可能是需要 $O(n^2)$ 的算法，因为 $1000^2=10^6$；
• 当 $n<100000$ 时，可能是需要 $O(nlo{g}_{2}n)$、$O(n(lo{g}_{2}n{)}^2)$ 的算法；
• 当 $n<1000000$ 时，可能是需要 $O(\sqrt{n})$、$O(n)$ 的算法；
• 细心的读者可能会发现，我在描述的时候都是用了可能的语气，那是因为以上数据量都是我通过做题总结出来的，有时候还需要结合题目本身的时间限制、出题人的阴险程度 来决定，所以不能一概而论。

• 关于 「 算法时间复杂度 」 的内容到这里就结束了。

• 有关?《画解数据结构》? 的源码均开源，链接如下：《画解数据结构》