分治算法简介

分治算法在编程教科书中并不常见，但它是每个程序员都应该了解的。分治算法是并发和多线程的支柱。

我经常听到有人说如何优化 for 循环使其更快，或者 switch 语句比 if 语句略快一些。大多数计算机都有多个核心，能够支持多线程。在担心优化 for 循环或 if 语句之前，不妨尝试从不同的角度来解决问题。

分治法是从不同角度解决问题的方法之一。在本文中，我将讨论如何创建分治解决方案以及它的含义。如果您对此主题没有任何经验或知识，也不用担心。本文旨在供编程知识很少的人阅读。

我将用三个例子来解释这一点。第一个例子会是一个简单的解释。第二个例子会是一些代码。最后一个例子会深入探讨分治法的数学核心。（别担心，我也讨厌数学。）

没时间读这篇文章？ 注册我的邮件列表，即可获取 PDF 格式。你还能获得一些本文未收录的额外内容 ✨点击此处注册。

什么是分而治之？🌎

分而治之就是把一个大问题分解成许多更容易解决的小问题。下面这个相对小的例子就说明了这一点。

我们取“3 + 6 + 2 + 4”这个等式，将其分解成尽可能小的方程组，即[3 + 6, 2 + 4]。它也可以是[2 + 3, 4 + 6]。顺序无关紧要，只要将这个长方程分解成许多更小的方程即可。

假设我们有 8 个数字：

我们要把它们全部加在一起。首先，我们把问题分成8个相等的子问题。具体做法是，把加法分解成单个数字。

然后我们开始一次添加 2 个数字。

然后将 4 个数字变成 8 个数字，这就是我们的结果。

为什么我们在第一阶段就把它分解成单个数字？为什么不直接从第二阶段开始呢？因为虽然这个数字列表是偶数，但如果列表是奇数，你就需要把它分解成单个数字才能更好地处理它。

分治算法试图将问题分解成尽可能多的小块，因为用小块更容易解决。它通常使用递归来实现这一点。

正式地讲，该技术正如Cormen、Leiserson、Rivest 和 Stein在著名的《算法导论》中所定义的那样：

划分

如果问题很小，就直接解决。否则，将问题分解成同一个问题的更小子集。

征服

通过递归求解较小的问题。如果子问题足够小，则无需递归，可以直接求解。

递归是指函数调用自身。如果你以前从未听说过递归，那么理解它可能会比较困难。本页面提供了很好的解释。简而言之，递归函数就是这样的：



n = 6

def recur_factorial(n):
   if n == 1:
       return n
   else:
       return n * recur_factorial(n-1)

print(recur_factorial(n))

我马上就会完整解释该代码。

结合

将子问题的解决方案合并为原始问题的解决方案。

对于上面的代码，需要注意一些重要事项。除法部分也是递归部分。我们将问题划分为return n * recur_factorial(n-1)。

具体来说，该recur_factorial(n-1)部分就是我们将问题进行划分的地方。

征服部分也是递归部分，但也是 if 语句。如果问题足够小，我们就直接求解（通过返回 n）。否则，我们执行return n * recur_factorial(n-1)。

合并。我们用乘法符号来做这件事。最终，我们返回该数的阶乘。如果那里没有这个符号，而它有，那么return recur_factorial(n-1)合并就不会进行，也不会输出任何类似于阶乘的东西。（感兴趣的朋友可以看看，它会输出 1）。

我们将探索分治法在一些著名算法、归并排序和汉诺塔解决方案中的工作原理。

合并排序🤖

归并排序是一种排序算法。该算法的工作原理如下：

将 n 个数字的序列分成两半
递归地对两半进行排序
将两个排序好的部分合并成一个排序好的序列

在这张图中，我们将这 8 个数字分解成单独的数字。就像我们之前做的那样。完成之后，我们就可以开始排序了。

它比较 51 和 13。由于 13 较小，所以它放在左侧。对 (10, 64)、(34, 5)、(32, 21) 都执行了同样的操作。

然后它将 (13, 51) 与 (10, 64) 合并。它知道 13 是第一个列表中最小的，而 10 是右边列表中最小的。10 小于 13，因此我们不需要比较 13 和 64。我们正在比较并合并两个已排序的列表。

在递归中，我们使用“基准情况”来指代我们能够处理的绝对最小值。对于归并排序，基准情况是 1。这意味着我们将列表拆分，直到得到长度为 1 的子列表。这也是为什么我们一直向下到 1 而不是 2。如果基准情况是 2，那么我们会在 2 处停止。

如果列表的长度 (n) 大于 1，那么我们将列表和每个子列表除以 2，直到得到大小为 1 的子列表。如果 n = 1，则列表已经排序，因此我们什么也不做。

归并排序是分治算法的一个例子。让我们再看一个算法，以真正理解分治算法的工作原理。

河内塔🗼

汉诺塔是一个数学问题，它由3个桩子（在本例中是3个圆盘）组成。这个问题主要用于教授递归，但在实际生活中也有一些用途。

每个圆盘的大小都不一样。我们要把所有圆盘都移到C柱上，最大的圆盘放在最下面，第二大的圆盘放在最大的圆盘上面，第三大的圆盘（最小的圆盘）放在所有圆盘的上面。这个游戏有一些规则：

我们每次只能移动 1 个圆盘。
圆盘不能放置在比它小的其他圆盘之上。

我们希望使用尽可能少的移动次数。如果我们有1个圆盘，我们只需要移动一次。如果我们有2个圆盘，我们需要移动3次。

移动次数是 2 的幂减 1。如果我们有 4 个圆盘，我们计算出最少移动次数为 2^4 = 16 - 1 = 15。

为了解决上述示例，我们需要将最小的圆盘存储在缓冲桩中（1 步）。下方动图展示了如何用 3 个桩和 3 个圆盘来解决汉诺塔问题。

请注意我们需要一个缓冲区来存储光盘。

我们可以把这个问题概括一下。假设我们有 n 个圆盘：递归地将 n-1 个圆盘从 A 移动到 B，将最大的圆盘从 A 移动到 C，再递归地将 n-1 个圆盘从 B 移动到 C。

如果棋子数量为偶数，则第一步总是移动到棋盘中间。如果棋子数量为奇数，则第一步总是移动到棋盘另一端。

让我们开始用伪代码编写 ToH 算法。



function MoveTower(disk, source, dest, spare):
    if disk == 0, then:
        move disk from source to dest

我们从一个基本情况开始，disk == 0。source是您开始的挂钩。dest是最终目的地挂钩。spare是备用挂钩。



FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
    move disk from source to dest
ELSE:
    MoveTower(disk - 1, source, spare, dest) // Step 1
    move disk from source to dest // Step 2
    MoveTower(disk - 1, spare, dest, source) // Step 3
END IF

请注意，在步骤 1 中，我们将dest和互换source。在步骤 3 中，我们不执行此操作。

通过递归，我们可以确定两件事：

它总是有一个基本情况（如果没有，算法如何知道结束？）
该函数调用自身。

算法在第 1 步和第 3 步有点令人困惑。它们都调用了同一个函数。这时就需要多线程了。你可以同时在不同的线程上运行第 1 步和第 3 步。

由于 2 大于 1，我们再次将其向下移动一级。到目前为止，你已经了解了分治法是什么。你应该了解它的工作原理以及代码是什么样子的。接下来，让我们学习如何使用分治法正式定义一个问题的算法。我认为这部分是最重要的。一旦你掌握了这一点，创建分治算法就会变得非常容易。

斐波那契数列🐰

斐波那契数列在自然界中随处可见。兔子的繁殖方式与斐波那契数列类似。2只兔子等于3，3只兔子等于5，5只兔子等于9，以此类推。

数字从 1 开始，下一个数字等于当前数字 + 前一个数字。这里是 1 + 0 = 1。然后 1 + 1 = 2。2 + 1 = 3，以此类推。

我们可以用递归来描述这种关系。递归是一个用较小输入定义函数的方程。递归和递归听起来很相似，实际上也类似。

对于斐波那契数列，如果 n = 0 或 1，结果为 1。否则，递归地将 f(n-1) + f(n -2) 相加，直到到达起始条件。让我们先创建一个非递归的斐波那契数列计算器。

我们知道如果 n = 0 或 1，则返回 1。



def f(n):
    if n == 0 or n == 1:
        return 1

斐波那契数列是最后两个数字相加的结果。



def f(n):
    if n == 0 or n == 1:
        return 1
    else:
    fibo = 1
    fibroPrev = 1
    for i in range (2, n):
        temp = fibo
        fibo = fibo + fiboPrev
        fiboPrev = temp
        return fibo

现在我们已经看到了这一点，让我们使用递归将其转换为递归。

创建递归时，我们总是从基本情况开始。这里的基本情况是，如果 n == 0 或 1，则返回 n。

如果我们不返回 n，而是返回 1，就会导致错误。例如，F(0) 的结果应该是 1。但实际上，它应该返回 0。

接下来，我们得到公式。如果 n 不是 0 或 1，我们该怎么办？我们计算 F(n - 1) + F(n - 2)。最后，我们要将所有数字合并在一起得到最终结果。我们使用加法来实现。

这是斐波那契数列的正式定义。通常，递归函数用于描述分治算法的运行时间。我和我的算法教授都认为，这实际上是创建分治算法的好工具。



def F(n):
  if n == 0 or n == 1:
    return n
  else:
    return F(n-1)+F(n-2)

有了分而治之的知识，上述代码更加清晰，更易于阅读。

我们经常使用执行树来计算递归的结果。计算机霸主🤖不需要这样做，但这对人类来说很有用，可以让他们了解分治算法是如何运作的。对于 F(4) 来说，它看起来像这样：

n 为 4，且 n 大于 0 或 1。因此，我们执行 f(n-1) + f(n-2)。我们暂时忽略加法运算。结果会产生两个新节点，分别是 3 和 2。3 大于 0 或 1，因此我们也执行相同的操作。2 也一样。我们重复此操作，直到得到一堆非 0 非 1 的节点。然后，我们将所有节点相加。1 + 1 + 0 + 0 + 1 = 3，这就是正确答案。

结论📕

一旦确定了如何将问题分解为多个较小的部分，就可以使用并发编程同时执行这些部分（在不同的线程上），从而加快整个算法的速度。

分治算法是提高算法速度最快、最简单的方法之一，在日常编程中非常有用。以下是我们在本文中讨论的最重要的主题：

什么是分而治之？
递归
归并排序
河内塔
编写分治算法
复发
斐波那契数列

下一步是探索多线程。选择你选择的编程语言，然后在谷歌上搜索“Python 多线程”作为示例。弄清楚它的工作原理，看看你是否可以从这个新角度解决你自己代码中的任何问题。

你还可以学习如何求解递归（找出递归的渐近运行时间），这是我即将撰写的下一篇文章。如果你不想错过，或者喜欢这篇文章，不妨考虑订阅我的邮件列表😁✨

在此订阅

文章来源：https://dev.to/brandonskerritt/a-gentle-introduction-to-divide-and-conquer-algorithms-1ga