算法思想(一):分治、回溯

递归

递归,去的过程叫“递”,回的过程叫“归”。能够用递归解决的问题都需要满足如下几个条件:

  • 存在递归终止条件
  • 一个问题可以分解为多个子问题
  • 问题和子问题,除了处了的数据规模不同,解决思路完全相同

我们需要找到将大问题分解为小问题的规律,并且基于此写抽象成一个递推公式,这个过程要注意,不要试图用人脑去分解递归的每个步骤,只要考虑当前层的逻辑。

使用递归还要注意重复计算问题,可以使用字典表缓存已经计算的结果。比方说爬楼梯问题暴力递归的时间复杂度是 O(2^n) ,在使用缓存之后时间复杂度就是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 递归代码模板
**/
public void recur(int level, int param) {
// 终结者
if (level > MAX_LEVEL) {
// process result
return;
}

// 当前层逻辑
process(level, param);

// 下一层
recur(level + 1, newParam);

// 重置当前状态
}

分治

分治就是“分而治之”,将原问题划分成 n 个规模较小而结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。用分治思想解决问题需要具有如下条件:

  • 原问题与分解成的小问题具有相同的模式

  • 原问题分解成的子问题可以独立求解,子问题之间没有相关性不会相互影响

  • 具有分解终止条件,也就是说,当问题足够小时,可以直接求解

  • 可以将子问题合并成原问题,但合并操作的复杂度不能太高,否则算法总体复杂度无法减小分

分治思想的代码包括 3 个步骤,分解、解决、合并:

  • 分解:将原问题分解为一系列子问题

  • 解决:递归地求解各个子问题,若子问题足够小,则直接求解

  • 合并:将子问题的结果合并成原问题的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 分治代码模板
* 求多数元素
**/
private int majorityElementRec(int[] nums, int low, int high) {
// Step1: 最小子问题, 可直接得出结果, 也是递归终止条件
// 这里就是将数组分解成只有一个元素
if (low == high) {
return nums[low];
}

// Step2: 准备数据
// 这里将数据一切为二
int mid = (high - low) / 2 + low;

// Step3: 问题分解并求出子问题
// 这里是分别求出左多数和右多数
int left = majorityElementRec(nums, low, mid);
int right = majorityElementRec(nums, mid + 1, high);

// Step4: 合并结果, 得出最终结果
// 这里是返回左右两边数量最多的数
if (left == right) {
return left;
}
int leftCount = countInRange(nums, left, low, high);
int rightCount = countInRange(nums, right, low, high);
return leftCount > rightCount ? left : right;

// Step5: 恢复状态
}

回溯

回溯就是采用试错的思想,从一组可能的解中,选择出一个满足要求的解。

  • 穷举所有的解,找到满足要求的解
    • 通过将问题分解为多个阶段(步骤),来穷举所有的可能解
    • 通过尝试发现当前的阶段的答案不能得到正确的解,将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的解
  • 利用剪枝操作,排除不需要穷举的情况,从而提高效率

总结

递归是解决问题一种手段属于编程技巧,而分治、回溯、贪心算法、动态规划属于算法思想。他们的关键是都是要找到问题的重复性。

分治思想的核心就是分而治之。在工程实践中 MapRedue 的本质就是分治,比方说 Spark 解决单机节点性能问题,将任务拆分到多个机器上处理,子任务之间互不干扰独立计算,最后再将合并结果。

回溯相当于穷举所有的情况,然后对比得到最优解。回溯算法的时间复杂度非常高,是指数级别。可以利用剪枝操作,排除不需要的分支,从而提高效率。

本周的算法思想并不难理解,关键是解决问题的时候能够找出问题的重复性,并且能够分解出子问题。“思想”总是高度抽象,想要灵活运用还是要多多练习这类的题目。