分治算法
提示
- 基本概念：分治算法通过将问题分解为更小的子问题，然后解决这些子问题并将它们组合来解决原始问题。
- 实现方式：通常使用递归来实现分治算法，例如在归并排序中，通过递归地分解数组并在排序后合并。
- 时间复杂度：分治算法的时间复杂度通常使用主定理计算，例如归并排序的时间复杂度为
O(n log n)。
分而治之算法是一种解决大问题的策略，它通过
- 将问题分解成更小的子问题
- 解决这些子问题，以及
- 将它们组合起来得到期望的输出。
要使用分而治之算法，通常会用到递归。了解不同编程语言中的递归：
想要正确学习递归吗？ 免费报名我们的互动式递归课程。
分而治之算法是如何工作的？
这里是涉及的步骤：
- 分解：使用递归将给定问题划分成子问题。
- 解决：递归地解决更小的子问题。如果子问题足够小，则直接解决。
- 组合：将作为递归过程一部分的子问题的解决方案组合起来，以解决实际问题。
让我们通过一个例子来理解这个概念。
这里，我们将使用分而治之的方法对数组进行排序（即归并排序）。
-
给定的数组为：
-
分解数组为两半。
再次递归地将每个子部分分解为两半，直到得到单个元素。
-
现在，以排序的方式组合单个元素。这里，解决和组合步骤并行进行。
时间复杂度
分而治之算法的复杂度是使用主定理计算的。
T(n) = aT(n/b) + f(n),
其中，
n = 输入的大小
a = 递归中子问题的数量
n/b = 每个子问题的大小。假设所有子问题都具有相同的大小。
f(n) = 递归调用外部完成的工作的成本，包括划分问题的成本和合并解决方案的成本
让我们举一个例子来找出递归问题的时间复杂度。
对于归并排序，方程可以写为：
T(n) = aT(n/b) + f(n)
= 2T(n/2) + O(n)
其中，
a = 2（每次将问题分解为2个子问题）
n/b = n/2（每个子问题的大小是输入的一半）
f(n) = 划分问题和合并子问题所需的时间
T(n/2) = O(n log n)（要理解这一点，请参考主定理。）
现在，T(n) = 2T(n log n) + O(n)
≈ O(n log n)
分治与动态规划
分治方法将问题分解为较小的子问题，然后递归地解决这些子问题。每个子问题的结果不会被保存以供将来使用，而在动态规划中，每个子问题的结果会被保存以备将来使用。
当相同的子问题不会被多次求解时，可采用分治方法。而当一个子问题的结果将来要被多次使用时，应使用动态规划方法。
让我们通过一个示例来理解这一点。假设我们试图找到斐波那契数列。然后，
分治方法:
fib(n)
If n < 2, return 1
Else , return f(n - 1) + f(n -2)
动态规划方法:
mem = []
fib(n)
If n in mem: return mem[n]
else,
If n < 2, f = 1
else , f = f(n - 1) + f(n -2)
mem[n] = f
return f
在动态规划方法中，mem 存储了每个子问题的结果。
分治算法的优点
- 使用朴素方法进行矩阵相乘的复杂度是
O(n3)，而使用分治方法（即 Strassen 的矩阵相乘）是O(n2.8074)。这种方法还简化了其他问题，如汉诺塔问题。 - 这种方法适用于多处理系统。
- 它有效地使用了内存缓存。