[每日一题]分治算法(Divid and Conquer)总结

从今天起，拒绝做一个平庸的程序员!引言这几天做的好几道关于 tree 的题都用到了分治算法，今天打算做一篇总...

这几天做的好几道关于 tree 的题都用到了分治算法，今天打算做一篇总结。

树是特别适合使用 分治算法，因为天然就具备“分割问题集”的属性。分治算法的方案往往比其他方案效率更高，更容易理解，代码也更简单。

今天的总结主要包括如下几个部分：

1. 分治算法的思想
2. 分治算法的套路
3. 典型例题分析

分治算法的基础是递归(递归是很多算法的基础，包括DP)， 它是递归的将问题分解成两个或者多个相同类型的子问题，直到这些子问题可以直接求解，然后在将这些子问题合并成原始问题的解。

三个步骤
1, 分(divide): 将原始问题分割成多个子问题，这些问题与原问题必须是同类型的，只是问题集更小一些。也就是说，分治算法要求问题本身是没有后效性(后效性的意思就是说当前的决策会对下一个决策产生影响)的。

2. 递归(recursion): 递归求解子问题

3. 治(conquer): 组合子问题，也就是 combine

特点
1. 并行性
因为可以独立的求解各个子问题，所以不同的子问题完全可以由不同的机器来处理。这样就可以充分利用CPU的计算能力，非常适合现在的分布式系统和多核CPU的架构。

2. 内存访问

分治算法能更好的利用内存的缓存机制。因为当子问题足够小的时候(n = 1 或者 0 )完全可以在缓存中求解，而不需要访问存取速度较慢的主存。

分治算法的这两个特点是函数式语言的基础，特别适合应用于函数式程序中。因为函数式语言没有对象，不需要维护状态，所以非常适合将复杂的问题分解成子问题，在分布式系统中运行。

举个例子：假设现在有一个任务: n 个文档，每个文档都是由 1 到 m 个单词组成的文本，现在需要些一个程序建一个的搜索引擎来方便查找这些文档数据。比如文本 x 中有 hello 单词，通过搜索 hello, 程序可以帮助我找到 x 文档。应用分治算法的思想，可以非常高效的处理这种类型问题。有空可以在单独写一篇文章来做说明。(补充一下，其实这就是 MapReduce 的基础)。

分治算法的应用

1. 二分查找
2. 排序
[list=1]
3. 归并排序
4. 快速排序

[*]中间值查找

[/*][*]树的问题

[/*][*]最大值和最小值

[/*][*]矩阵乘法

[/*][*]最近点问题

[/*][*]...

[/*][/list]

套路

伪代码如下

DivdeAndConquer(P) {

if 问题P足够的小了，不可在分了:

return  solution(P) #处理结果

将问题P分割成n个子问题: P1, P2, ... , Pn

return  combile( DivdeAndConquer(P1), DivdeAndConquer(P2)... DivdeAndConquer(pn)

}

从套路中可以看出，分治算法的难点和技巧在于：怎么分 和 怎么合。
下面我们会集中做4到题来学习分治算法的解题思路和技巧。

问题描述

已知由n个数组成的数组 A, 找出一个连续的子序列，且该子序列中元素之和为所有的连续子序列中最大。比如 [ -2, 11, -4, 13, -5, 2] 的最大连续子序列是 11 + (-4) + 13 = 20

思路

子问题是什么？如果没有思路，我们可以假设子问题的大小就是 n / 2。那么有如下三种可能:
1. 结果在数组的左边

2. 结果在数组的右边

3. 结果在数组的中间
对于1，2子问题，只需要递归就行了，只有3需要特殊处理。

问题描述
快速排序法

思路

1. 选择数组的第一个元素作为标志元素
2. 小于第一个元素的值放左边(会生成新的数组，也就是子问题)
3. 大于第一个元素的值放右边(会生成新的数组，也就是子问题)
4. 递归的求解左右两边的子数组

问题描述

求 k 的 n 次幂，比如 2 的 3 次幂 等于 8

思路

求解k的n次幂，就是求解两个 k 的 n / 2 次幂的乘积 或者 k 的 n次幂 和 k 的乘积

问题描述
已知包含 2n 个整数的数组 a1a2a3...an b1 b2 b3...bn, 不使用额外的内存空间将数组打乱成 a1b1a2b2...anbn

注意: n 是 2 的倍数

思路
1. 假设数组是 a1, a2, a3, a4, b1, b2, b3, b4

2. 将数组分成两个部分 a1, a2, a3, a4 : b1, b2, b3, b4

3. 从中心处将元素交换 a3, a4 跟 b1, b2 交换 -》a1, a2, b1, b2, a3, a4, b3, b4
4. 递归求解即可

今天主要分享了分治算法的思路和套路。分治算法思想在高性能计算领域的应用非常广泛，是一个非常基础核心的算法思想，值得深入研究。欢迎加入每日一题二群，一群已满。在一群的伙伴就不要重复的加了~

    关注 一个技术人员的胡言乱语