Posted on

如何确定代码源文件的编译依赖关系

我们知道，一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp 依赖 B.cpp，那在编译的时候，编译器需要先编译 B.cpp，才能编译 A.cpp。编译器通过分析源文件或者程序员事先写好的编译配置文件（比如 Makefile 文件），来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢：

算法解析

我们在穿衣服的时候都有一定的顺序，我们可以把这种顺序想成，衣服与衣服之间有一定的依赖关系。比如说，你必须先穿袜子才能穿鞋，先穿内裤才能穿秋裤。假设我们现在有八件衣服要穿，它们之间的两两依赖关系我们已经很清楚了，那如何安排一个穿衣序列，能够满足所有的两两之间的依赖关系？这就是个拓扑排序（Topological Sorting）问题。从这个例子中，你应该能想到，在很多时候，拓扑排序的序列并不是唯一的：

Read more »

Posted on

动态规划学习路线

动态规划（Dynamic Programming）比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。不过，它也是出了名的难学。它的主要学习难点跟递归类似，那就是，求解问题的过程不太符合人类常规的思维方式。对于新手来说，要想入门确实不容易。不过，等你掌握了之后，你会发现，实际上并没有想象中那么难。

0-1 背包问题

对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢。关于这个问题，回溯的解决方法就是穷举搜索所有可能的装法，然后找出满足条件的最大值。不过，回溯算法的复杂度比较高，是指数级别的。那有没有什么规律，可以有效降低时间复杂度呢：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 回溯算法实现。注意：我把输入的变量都定义成了成员变量
private int maxW = Integer.MIN_VALUE;   // 结果放到 maxW 中
private int[] weight = {2, 2, 4, 6, 3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
public void f(int i, int cw) { 
    // 调用 f(0, 0)
    if (cw == w || i == n) { 
        // cw==w 表示装满了，i==n 表示物品都考察完了
        if (cw > maxW) {
            maxW = cw;
        }
        return;
    }
    f(i+1, cw); // 选择不装第 i 个物品
    if (cw + weight[i] <= w) {
        f(i+1, cw + weight[i]); // 选择装第 i 个物品
    }
}
Read more »

Posted on

如何理解“回溯算法”？

笼统地讲，回溯算法（Backtracking Algorithm）很多时候都应用在“搜索”这类问题上。不过这里说的搜索，并不是狭义的指我们前面讲过的图的搜索算法，而是在一组可能的解中，搜索满足期望的解。回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。你可以看我画的图，第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式：

我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行, 第二行, 第三行, …, 第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试。回溯算法非常适合用递归代码实现：

Read more »

Posted on

MapReduce 是 Google 大数据处理的三驾马车之一，另外两个是 GFS 和 Bigtable。它在倒排索引、PageRank 计算、网页分析等搜索引擎相关的技术中都有大量的应用。

如何理解分治算法？

分治算法（Divide-and-Conquer Algorithm）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

  • 分解：将原问题分解成一系列子问题；
  • 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
  • 合并：将子问题的结果合并成原问题；

分治算法能解决的问题，一般需要满足下面这几个条件：

  • 原问题与分解成的小问题具有相同的模式；
  • 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
  • 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
  • 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了；
Read more »

Posted on

如何理解“贪心算法”？

假设我们有一个可以容纳 100kg 物品的背包，可以装各种物品。我们有以下 5 种豆子，每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢：

实际上，这个问题很简单，我们只要先算一算每个物品的单价，按照单价由高到低依次来装就好了。单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆，所以，我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。这个问题的解决思路显而易见，它本质上借助的就是贪心算法。

贪心算法（Greedy Algorithm）解决问题的步骤：

  1. 针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。类比到刚刚的例子，限制值就是重量不能超过 100kg，期望值就是物品的总价值。这组数据就是 5 种豆子。我们从中选出一部分，满足重量不超过 100kg，并且总价值最大；
  2. 每次选择当前情况下，对限制值同等贡献量，并对期望值贡献最大的数据。类比到刚刚的例子，我们每次都从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子；
  3. 严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。大部分情况下，举几个例子验证一下就可以了；
Read more »