分治思想与分治算法的区别

引言：分治，即分而治之，是“先分解、再各个击破”的意思，分为“分”和“治”两个步骤。然而在计算机科学中，当我们介绍分治算法的时候，我们往往说分治算法分为3步，即“分解、解决、合并”。为什么明明分治思想只有2步，而分治算法却有3步，分治思想与分治算法有什么区别和联系呢？

“分治思想”作为一种抽象的哲学或方法论，其本身的核心确实是“分”和”治”这两个步骤。而“使用分治思想的算法”是一种具体的实现，它把对原问题的求解分解为子问题的求解，并通过子问题的解构建原问题的解，这个构建的过程我们称之为“合并”。如果仅仅是获得子问题的解，那么就只有2步，如果要获得原问题的解，那么就需要第3步。

我们可以这样比喻：

分治思想：就像“先分解，再逐个击破”的战略思想。

分治算法：则是应用这一思想，包含了“分解、击破、组合成果”的具体战术方案。

1. 分治思想本身：纯粹的“战略”

在最抽象、最哲学的层面上，分治（Divide and Conquer）是一种处理复杂问题的策略：

分（Divide）：将一个大而复杂的问题分解成若干个规模更小、结构相同、更容易解决的子问题。

治（Conquer）：递归地解决这些子问题。如果子问题仍然足够大，就继续分解；如果子问题已经足够小、足够简单，就直接求解。

在这个层面，它只有两步。分治思想本身关注的是“如何通过分解来降低问题复杂度”，它并不规定解决子问题后该怎么办。“合并”并不是思想的一部分，而是实现该思想时产生的必然需求。

2. 分治算法：具体的“战术”

当我们将这种思想转化为具体的算法（特别是用于计算问题的算法）时，情况就发生了变化。绝大多数情况下，我们分解问题不是为了解决子问题本身，而是为了利用子问题的解来构造原问题的解。

因此，一个完整的分治算法几乎总是包含三个步骤：

• 分解（Divide）：将原问题分解为若干个规模较小的子问题。
• 解决（Conquer）：递归地求解子问题。若子问题规模足够小，则直接求解。
• 合并（Combine）：将子问题的解合并成原问题的解。

为什么“合并”这一步在算法中不可或缺？

因为“分”和“治”之后，我们得到的是一个个孤立的子问题的答案。而原始问题是一个整体，它需要一个统一的答案。“合并”就是搭建从子答案通往总答案的桥梁。没有这一步，分治就失去了意义。

让我们用经典的归并排序（Merge Sort） 来验证：

• 分（Divide）：将当前数组一分为二，得到左半部分和右半部分两个子数组。
• 治（Conquer）：递归地对左半部分和右半部分进行排序。
• 合（Combine）：这是最关键的一步！将两个已经排序好的子数组合并成一个新的有序数组。如果没有这一步，即使左右两边都排好了序，整个数组依然是无序的。

在这个例子中，“合并”不仅仅是步骤之一，它甚至是整个算法的核心和耗时的操作。

3. 分治算法总是有合并这一步吗？

从逻辑上讲，分治算法的第二步只是获得了子问的解，而我们的最终目标是要获得原问题的解，所以从子问题的解到原问题的解，一定需要一个过程。但是，在某些特殊情况下，子问题的解就是原问题的解，因而也许用文字描述时，可以用一句“因而原问题的解就是xxx”来概括，而在代码里，则没有这一步。换句话说，合并这一步，在逻辑上是存在的，而在具体操作中（包括代码中）则可能不存在（或者说是隐式的）。

例如，在快速排序中：

• 分：选择一个基准（pivot），进行分区（Partition）操作。这个操作极其关键：它将数组重排，使得所有小于基准的元素在其左边，大于基准的在其右边。请注意，这个操作本身就在“构建”最终有序数组的雏形！ 基准元素被放到了它最终应该在的位置上。
• 治：递归地对基准左边和右边的子数组进行快速排序。
• 合：需要合并吗？不需要。为什么？因为“合并”的工作已经在分区（Partition） 这一步隐式地完成了！当左右子数组都排好序时，由于基准已经在正确位置，且左边全小于右边，所以整个数组天然就是有序的。无需任何额外的组合操作。

快速排序的“分”是聪明的、做了大量工作的“分”，而归并排序的“分”是愚蠢的、简单的“分”。

再比如，在二分查找中：

• 分：选择中间元素，将问题分为“左半部分”、“中间元素”、“右半部分”三个子问题。
• 治：判断目标值与中间元素的关系。
  1. 如果相等，问题已解决，返回当前索引。
  2. 如果小于，选择左半部分进行递归。
  3. 如果大于，选择右半部分进行递归。
• 合：需要合并吗？不需要。因为算法不是在“组合”答案，而是在“选择”答案。最终的解要么是中间元素本身，要么是某一个子问题的解。它只是简单地将子问题的解（或空）返回给上级调用者。

二分查找的“合”可以理解为一种“选择”或“传递”，而不是“合并”。

4. 总结

分治思想是战略，思想本身只有2步；分治算法是战术，分治算法采用了分治思想，把大问题的求解转化成小问题的求解，但最终目标是要得到大问题的解，因而需要3步。

大家有什么不同想法吗？欢迎留言讨论。

本文为学漄乐码学堂所撰。要了解学漄乐码更多信息，请查看博主简介。