算法

我们可以认为解决任何一个问题可以分为多个处理点，该处理点需要寻找向前的多个处理点或者向后的多个处理点。 而在回溯中，我们可能为该点先选定某个状态，然后直接按照该状态递归进入下一层，在所有后向的处理点处理完毕之后，将该状态以及该状态相关的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后输出本次问题规模和对应的运行时间。运行以上程序得到的输出如下所示：

250 0.0
500 0.1
1000 0.6
2000 4.3
4000 30.6

上面的输出之所以和理论值有所出入是因为实际运行环境是复杂多变的，因而会产生许多偏差，尽可能减小这种偏差的方式就是多次运行以上程序并取平均值。有了上面这个热身的小程序做铺垫，接下来我们就可以正式介绍这个“可以简单有效地预测任意程序执行性能并判断其运行时间的大致增长数量级”的方法了，实际上它的工作基于以上的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).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地 址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变 量。

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