复杂度分析

算法

我们可以认为解决任何一个问题可以分为多个处理点，该处理点需要寻找向前的多个处理点或者向后的多个处理点。而在回溯中，我们可能为该点先选定某个状态，然后直接按照该状态递归进入下一层，在所有后向的处理点处理完毕之后，将该状态以及该状态相关的 Side Effect 清空，从而进入下一个处理。

搜索(DFS/BFS)、动态规划与回溯递归我们常用的手段，在任何多点组成的图/树/棋盘中，如果单个点有多种可能性，譬如数独类题目，那么需要搜索+回溯，不过这种题目一般可以按顺序搜索。而对于迷宫、树、图类，其在搜索时，往往单个点仅有一个值，因此不需要进行回溯，而需要建立栈/队列等辅助的工具进行搜索，因为其处理指针的移动顺序不是按序移动。

回溯时，如果我么希望找出全部解，则每个迭代函数的返回值为空。如果仅希望找到一个解，那么迭代函数返回值为 true/false。

贪心策略是我们常用的算法策略之一，譬如在最小生成树的 Prim 算法、Kruskal 算法与 Dijkstra 算法中都使用到了贪心策略。

动态规划问题核心在于确定变量与状态转化公式。典型的变量譬如两个字符串比较中的截取的字串长度 i，j，那么可以构建出一个二维的备忘录。而典型的 01 背包问题中，自变量也有背包的容量 m 与物品的数目 n。而如果自变量数目比较多时，譬如在股票 K 次买卖问题中，存在三个自变量：天数 i、买卖次数 k 以及某天是否为持有/不持有 h，此时不建议建立三维数组，还是以多个备忘录方式会比较好。而状态转化公式也存在两种考虑，一个是前向公式，一个是后向公式。在典型的 LCS 问题中，直观的状态转化公式是

而在 WalkToArray 中，状态转化公式则是后向推导，即在处理点 i 处向后更新之后所有其可达到点的最短步数的值。

动态规划类题目每种情况也是仅有一个可行解，因此可以利用分治+备忘录的方式来将复杂问题抽象为简单问题的累加。一般是自顶向下，即从最简单问题开始可以慢慢推导出复杂情况。而递归类问题则是自底向上，即我们

总结而言，一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的：

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

课程大纲暂定如下，后续会有微调，具体以实际上课内容为准： 1、C/C++语言梳理数组和指针在参数传递中的异同深刻理解递归 C++ STL

2、链表、递归、栈链表环、共同结点等的判定直方图最大矩形面积/有向图的拓扑排序逆波兰表达式/括号匹配问题及其变种

3、字符串循环位移问题详解最长公共子序列 LCS 详解字符串的全排列的四个问题 KMP 字符串的查找

4、数组 Top10 问题寻优最大连续子数组 X-Sum(子集和数问题)：2-sum、n-sum 等 N 指针方法：奇偶排序、荷兰国旗等深化循环不变式

5、树二叉搜索树删除二叉树的遍历(递归、非递归) 详解平衡二叉树(AVL 树) 2-3-4 树、红黑树 B 树/R 树

6、图 Bellman-Ford 算法/Dijkstra 算法/Folyd 算法最小生成树(Prim 算法、Kruskal 算法) 实践应用：Word-Ladder/马踏棋盘/数独问题/N-皇后问题

7、查找排序无 bug 二分查找的实现与技巧行列递增杨氏矩阵的查找归并排序/快速排序/堆排序及其应用基数排序/记数排序/桶排序及其应用

8、贪心和动态规划从机器学习的角度统一贪心法和动态规划贪心的应用：任务安排问题、甘特图走棋盘-及其实践中的重要应用典型 DP 应用：格子取数问题/字符串的交替连接/矩阵连乘/背包问题数零钱问题/回文划分问题/单词划分问题

9、概率组合数论统计现实中的概率问题：以麻将为例用动态规划推导组合公式圆内/任意多边形均匀取点问题歌曲、商品等推荐问题金钗赠诗问题/树型状态

10、BAT 海量数据处理、系统设计题精讲 Darts 高效索引 Hash 和树的综合：POI 问题详解跳跃表/BloomFitler 遗传算法/蚁群算法

时间复杂度

时间复杂度用来检验某个算法处理一定量的数据要花多长时间。为了描述这个复杂度，主要有相关的三种符号记法：

第一种叫 Big O notation，它给出了运行时间的”渐进上界“，也就是算法在最坏情况下运行时间的上限。它的定义如下：对于 f(n)和 g(n)，若存在常数 c 和 N0，使得对于所有 n > N0，都有 |f(n)| < c * g(n)，则称 f(n)为 O(g(n))。
第三种叫做 Big Ω notation，它给出了运行时间的“渐进下界”，也就是算法在最坏情况下运行时间的下限。它的定义如下：对于 f(n)和 g(n)，若存在常数 c 和 N0，使得对于所有 n > N0，都有|f(n)| > c * g(n)，则称 f(n)为 Ω(g(n))。
第三种叫 Big Θ notation，它确定了运行时间的”渐进确界“。定义如下：对于 f(n)和 g(n)，若存在常数 c 和 N0，对于所有 n> N0，都有|f(n)| = c * g(n)，则称 f(n)为 Θ 为 Θ(g(n))。

在平常的算法分析中最常用到的是 Big O notation，这个表示法用一个函数来描述算法处理给定的数据需要多少次运算。比如，当我说这个算法是适用 O(某函数())，我的意思是对于某些数据，这个算法需要某函数(数据量) 次运算来完成。重要的不是数据量，而是 当数据量增加时运算如何增加。时间复杂度不会给出确切的运算次数，但是给出的是一种理念。

图中可以看到不同类型的复杂度的演变过程，我用了对数尺来建这个图。具体点儿说，数据量以很快的速度从 1 条增长到 10 亿条。我们可得到如下结论：

绿：O(1)或者叫常数阶复杂度，保持为常数(要不人家就不会叫常数阶复杂度了)。
红：O(log(n))对数阶复杂度，即使在十亿级数据量时也很低。
粉：最糟糕的复杂度是 O(n^2)，平方阶复杂度，运算数快速膨胀。
黑和蓝：另外两种复杂度(的运算数也是)快速增长。

O

简明解释算法中的大 O 符号

Common Algorithms Complexity:常见算法复杂度

bigoposter

Data Structure Operations

Array Sorting Algorithms

Graph Operations

Heap Operations

分析方法

一个算法的运行时间也就是执行所有程序语句的耗时总和。然而在实际的分析中，我们并不需要考虑所有程序语句的运行时间，我们应该做的是集中注意力于最耗时的部分，也就是执行频率最高而且最耗时的操作。也就是说，在对一个程序的时间复杂度进行分析前，我们要先确定这个程序中哪些语句的执行占用的它的大部分执行时间，而那些尽管耗时大但只执行常数次(和问题规模无关)的操作我们可以忽略。我们选出一个最耗时的操作，通过计算这些操作的执行次数来估计算法的时间复杂度，下面我们来具体介绍这一过程。

public static int count(int[] a) {
  int N = a.length;
  int cnt = 0;
  for (int i = 0; i < N; i++) {
  for (int j = i + 1; j < N; j++) {
  for (int k = j + 1; k < N; k++) {
  if (a[i] + a[j] + a[k] == 0) {
  cnt++;
  }
  }
  }
  }
  return cnt;
  }

首先我们看到以上代码的第 1 行和第 2 行的语句只会执行一次，因此我们可以忽略它们。然后我们看到第 4 行到第 12 行是一个三层循环，最内存的循环体包含了一个 if 语句。也就是说，这个 if 语句是以上代码中耗时最多的语句，我们接下来只需要计算 if 语句的执行次数即可估计出这个算法的时间复杂度。以上算法中，我们的问题规模为 N(输入数组包含的元素数目)，我们也可以看到，if 语句的执行次数与 N 是相关的。我们不难得出，if 语句会执行 N _ (N - 1) _ (N - 2) / 6 次，因此这个算法的时间复杂度为 O(n^3)。这也印证了我们之前猜想的运行时间与问题规模的函数关系(T(n) = k * n ^ 3)。通过以上分析，我们知道分析算法的时间复杂度只需要两步：

寻找执行次数多的语句作为决定运行时间的[关键操作];
分析关键操作的执行次数。

倍率实验

下面我们来介绍一下算法(第 4 版) (豆瓣)一书中的“倍率实验”。这个方法能够简单有效地预测程序的性能并判断他们的运行时间大致的增长数量级。在正式介绍倍率实验前，我们先来简单介绍下“增长数量级“这一概念(同样引用自《算法》一书)：

我们用~f(N)表示所有随着 N 的增大除以 f(N)的结果趋于 1 的函数。用 g(N)~f(N)表示 g(N) / f(N)随着 N 的增大趋近于 1。通常我们用到的近似方式都是 g(N) ~ a * f(N)。我们将 f(N)称为 g(N)的增长数量级。

我们还是拿 ThreeSum 程序来举例，假设 g(N)表示在输入数组尺寸为 N 时执行 if 语句的次数。根据以上的定义，我们就可以得到 g(N) ~ N ^ 3(当 N 趋向于正无穷时，g(N) / N^3 趋近于 1)。所以 g(N)的增长数量级为 N^3，即 ThreeSum 算法的运行时间的增长数量级为 N^3。

现在，我们来正式介绍倍率实验(以下内容主要引用自上面提到的《算法》一书，同时结合了一些个人理解)。首先我们来一个热身的小程序：

public class DoublingTest {
  public static double timeTrial(int N) {
  int MAX = 1000000;
  int[] a = new int[N];
  for (int i = 0; i < N; i++) {
  a[i] = StdRandom.uniform(-MAX, MAX);
  }
  long startTime = System.currentTimeMillis();
  int count = ThreeSum.count(a);
  long endTime = System.currentTimeMillis();
  double time =(endTime - startTime) / 1000.0;
  return time;
  }

  public static void main(String[] args) {
  for (int N = 250; true; N += N) {
  double time = timeTrial(N);
  StdOut.printf("%7d %5.1f\n", N, time);
  }
  }
}

以上代码会以 250 为起点，每次讲 ThreeSum 的问题规模翻一倍，并在每次运行 ThreeSum 后输出本次问题规模和对应的运行时间。运行以上程序得到的输出如下所示：

上面的输出之所以和理论值有所出入是因为实际运行环境是复杂多变的，因而会产生许多偏差，尽可能减小这种偏差的方式就是多次运行以上程序并取平均值。有了上面这个热身的小程序做铺垫，接下来我们就可以正式介绍这个“可以简单有效地预测任意程序执行性能并判断其运行时间的大致增长数量级”的方法了，实际上它的工作基于以上的 DoublingTest 程序，大致过程如下：

开发一个[输入生成器]来产生实际情况下的各种可能的输入。
反复运行下面的 DoublingRatio 程序，直至 time/prev 的值趋近于极限 2^b，则该算法的增长数量级约为 N^b(b 为常数)。

DoublingRatio 程序如下：

运行倍率程序，我们可以得到如下输出：

250 0.0 2.0
500 0.1 5.5
1000 0.5 5.4
2000 3.7 7.0
4000 27.4 7.4
8000 218.0 8.0

我们可以看到，time/prev 确实收敛到了 8(2^3)。那么，为什么通过使输入不断翻倍而反复运行程序，运行时间的比例会趋于一个常数呢？答案是下面的[倍率定理]:

若 T(N) ~ a _ N^b _ lgN，那么 T(2N) / T(N) ~2^b。

以上定理的证明很简单，只需要计算 T(2N) / T(N)在 N 趋向于正无穷时的极限即可。其中，“a _ N^b _ lgN”基本上涵盖了常见算法的增长量级(a、b 为常数)。值得我们注意的是，当一个算法的增长量级为 NlogN 时，对它进行倍率测试，我们会得到它的运行时间的增长数量级约为 N。实际上，这并不矛盾，因为我们并不能根据倍率实验的结果推测出算法符合某个特定的数学模型，我们只能够大致预测相应算法的性能(当 N 在 16000 到 32000 之间时，14N 与 NlgN 十分接近)。

Example

前面我们介绍了算法分析的一些姿势，那么现在我们就来学以致用，一起来解决几道一线互联网企业有关于算法分析的面试/笔试题。

【腾讯】下面算法的时间复杂度是____

int foo(int n) {

if (n <= 1) {

return 1；

}

return n * foo(n - 1);

}

看到这道题要我们分析算法时间复杂度后，我们要做的第一步便是确定关键操作，这里的关键操作显然是 if 语句，那么我们只需要判断 if 语句执行的次数即可。首先我们看到这是一个递归过程：foo 会不断的调用自身，直到 foo 的实参小于等于 1，foo 就会返回 1，之后便不会再执行 if 语句了。由此我们可以知道，if 语句调用的次数为 n 次，所以时间复杂度为 O(n)。

【京东】以下函数的时间复杂度为____

void recursive(int n, int m, int o) {

if (n <= 0) {

printf("%d, %d\n", m, o);

} else {

recursive(n - 1, m + 1, o);

recursive(n - 1, m, o + 1);

}

}

这道题明显要比上道题难一些，那么让我们来按部就班的解决它。首先，它的关键操作时 if 语句，因此我们只需判断出 if 语句的执行次数即可。以上函数会在 n > 0 的时候不断递归调用自身，我们要做的是判断在到达递归的 base case(即 n <= 0)前，共执行了多少次 if 语句。我们假设 if 语句的执行次数为 T(n, m, o)，那么我们可以进一步得到：T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) (当 n > 0 时)。我们可以看到 base case 与参数 m, o 无关，因此我们可以把以上表达式进一步简化为 T(n) = 2T(n-1)，由此我们可得 T(n) = 2T(n-1) = (2^2) * T(n-2)……所以我们可以得到以上算法的时间复杂度为 O(2^n)。

【京东】如下程序的时间复杂度为____(其中 m > 1，e > 0)

x = m;

y = 1;

while (x - y > e) {

x = (x + y) / 2;

y = m / x;

}

print(x);

以上算法的关键操作即 while 语句中的两条赋值语句，我们只需要计算这两条语句的执行次数即可。我们可以看到，当 x - y > e 时，while 语句体内的语句就会执行，x = (x + y) / 2 使得 x 不断变小(当 y«x 时，执行一次这个语句会使 x 变为约原来的一半)，假定 y 的值固定在 1，那么循环体的执行次数即为~logm，而实际情况是 y 在每次循环体最后都会被赋值为 m / x，这个值总是比 y 在上一轮循环中的值大，这样一来 x-y 的值就会更小，所以以上算法的时间复杂度为 O(logm)。

【搜狗】假设某算法的计算时间可用递推关系式 T(n) = 2T(n/2) + n，T(1) = 1 表示，则该算法的时间复杂度为____

根据题目给的递推关系式，我们可以进一步得到：T(n) = 2(2T(n/4) + n/2) + n = … 将递推式进一步展开，我们可以得到该算法的时间复杂度为 O(nlogn)，这里就不贴上详细过程了。

算法复杂度

时间复杂度

一个算法执行所耗费的真实时间称为时间频度，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。时间复杂度在刚才提到的时间频度中，n 称为问题的规模，当 n 不断变化时，时间频度 T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模 n 的某个函数，用 T(n)表示，若有某个辅助函数 f(n),使得当 n 趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。记作 T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。时间频度不同，但时间复杂度可能相同。如：T(n)=n2+3n+4 与 T(n)=4n2+2n+1 它们的频度不同，但时间复杂度相同，都为 O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶 O(1),对数阶 O(log2n),线性阶 O(n), 线性对数阶 O(nlog2n),平方阶 O(n2)，立方阶 O(n3),…，k 次方阶 O(nk),指数阶 O(2n)。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。在最坏情况下的时间复杂度为 T(n)=0(n)，它表示对于任何输入实例,该算法的运行时间不可能大于 0(n)。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。指数阶 0(2n)，显然，时间复杂度为指数阶 0(2n)的算法效率极低，当 n 值稍大时就无法应用。

如果算法的执行时间不随着问题规模 n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是 O(1)。 x=91; y=100; while(y>0) if(x>100) {x=x-10;y–;} else x++; 解答: T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了 1100 次，但是我们看到 n 没有? 没。这段程序的运行是和 n 无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度 f(n)决定的。 x=1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x++; 　　该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模 n 没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与 n 有关，因此可以从内层循环向外层分析语句(5)的执行次数: 则该程序段的时间复杂度为 T(n)=O(n3/6+低次项)=O(n3)

算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。在数值 A[0..n-1]中查找给定值 K 的算法大致如下: i=n-1; while(i>=0&&(A[i]!=k)) i–; return i; 此算法中的语句(3)的频度不仅与问题规模 n 有关，还与输入实例中 A 的各元素取值及 K 的取值有关: ① 若 A 中没有与 K 相等的元素，则语句(3)的频度 f(n)=n；② 若 A 的最后一个元素等于 K,则语句(3)的频度 f(n)是常数 0。

递归算法时间复杂度推导

一般来说，在递归算法中的时间复杂度可以表示为: $T[n] = aT[n/b] + f(n) $

快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然我上面的不是)；此时的时间复杂度公式则为：$T[n] = 2T[n/2] + f(n)$；$T[n/2]$为平分后的子数组的时间复杂度，$f[n]$为平分这个数组时所花的时间；

$$ T(n)≤2T(n/2) +n，T(1)=0\ T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n\ T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n\ ……\ T(n)≤nT(1)+(log2n)×n= O(nlogn) \ $$

空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。　　 (1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。 (2)可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用 f(n)表示。S(n)=O(f(n))　　其中 n 为问题的规模，S(n)表示空间复杂度。当一个算法的空间复杂度为一个常量，即不随被处理数据量 n 的大小而改变时，可表示为 O(1)；当一个算法的空间复杂度与以 2 为底的 n 的对数成正比时，可表示为 0(10g2n)；当一个算法的空 I 司复杂度与 n 成线性比例关系时，可表示为 0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。

最近更新于 0001-01-01