那么，我们不禁发问：为什么分治可以提升算法效率，其底层逻辑是什么？换句话说，将大问题分解为多个 子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。 操作数量优化 以「冒泡排序」为例，其处理一个长度为 ? 的数组需要 ?(?2) 时间。假设我们把数组从中点分为两个子数 组，则划分需要 ?(?) 时间，排序每个子数组需要 ?(( log ?) 。 再思考，如果我们多设置几个划分点，将原数组平均划分为 ? 个子数组呢？这种情况与「桶排序」非常类似， 它非常适合排序海量数据，理论上时间复杂度可以达到 ?(? + ?) 。 并行计算优化 我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的 时间复杂度，还有利于操作系统的并行优化。 并行优化在多核或多处理器的环境中尤其有效，因为 源，从而显著减少总体的运行时间。 比如在桶排序中，我们将海量的数据平均分配到各个桶中，则可所有桶的排序任务分散到各个计算单元，完 成后再进行结果合并。 Figure 12‑3. 桶排序的并行计算 12.1.3. 分治常见应用 一方面，分治可以用来解决许多经典算法问题： ‧ 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后再找出跨越两 部分的最近点对。

那么，我们不禁发问：为什么分治可以提升算法效率，其底层逻辑是什么？换句话说，将大问题分解为多个 子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。 1. 操作数量优化 以“冒泡排序”为例，其处理一个长度为 ? 的数组需要 ?(?2) 时间。假设我们按照图 12‑2 所示的方式，将 数组从中点处分为两个子数组，则划分需要 ?) 。 再思考，如果我们多设置几个划分点，将原数组平均划分为 ? 个子数组呢？这种情况与“桶排序”非常类似， 它非常适合排序海量数据，理论上时间复杂度可以达到 ?(? + ?) 。 2. 并行计算优化 我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的 时间复杂度，还有利于操作系统的并行优化。 并行优化在多核或多处理器的环境中尤其有效，因为 源，从而显著减少总体的运行时间。 比如在图 12‑3 所示的“桶排序”中，我们将海量的数据平均分配到各个桶中，则可所有桶的排序任务分散到 各个计算单元，完成后再合并结果。 图 12‑3 桶排序的并行计算 12.1.3 分治常见应用 一方面，分治可以用来解决许多经典算法问题。 ‧ 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后找出跨越两部 分的最近点对。 ‧

那么，我们不禁发问：为什么分治可以提升算法效率，其底层逻辑是什么？换句话说，将大问题分解为多个 子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。 1. 操作数量优化 以“冒泡排序”为例，其处理一个长度为 ? 的数组需要 ?(?2) 时间。假设我们按照图 12‑2 所示的方式，将 数组从中点处分为两个子数组，则划分需要 ?) 。 再思考，如果我们多设置几个划分点，将原数组平均划分为 ? 个子数组呢？这种情况与“桶排序”非常类似， 它非常适合排序海量数据，理论上时间复杂度可以达到 ?(? + ?) 。 2. 并行计算优化 我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的 时间复杂度，还有利于操作系统的并行优化。 并行优化在多核或多处理器的环境中尤其有效，因为 源，从而显著减少总体的运行时间。 比如在图 12‑3 所示的“桶排序”中，我们将海量的数据平均分配到各个桶中，则可将所有桶的排序任务分散 到各个计算单元，完成后再合并结果。 图 12‑3 桶排序的并行计算 12.1.3 分治常见应用 一方面，分治可以用来解决许多经典算法问题。 ‧ 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后找出跨越两部 分的最近点对。 ‧

那么，我们不禁发问：为什么分治可以提升算法效率，其底层逻辑是什么？换句话说，将大问题分解为多个 子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。 1. 操作数量优化 以“冒泡排序”为例，其处理一个长度为 ? 的数组需要 ?(?2) 时间。假设我们按照图 12‑2 所示的方式，将 数组从中点分为两个子数组，则划分需要 ?( ?) 。 再思考，如果我们多设置几个划分点，将原数组平均划分为 ? 个子数组呢？这种情况与“桶排序”非常类似， 它非常适合排序海量数据，理论上时间复杂度可以达到 ?(? + ?) 。 2. 并行计算优化 我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的 时间复杂度，还有利于操作系统的并行优化。 并行优化在多核或多处理器的环境中尤其有效，因为 源，从而显著减少总体的运行时间。 比如在图 12‑3 所示的“桶排序”中，我们将海量的数据平均分配到各个桶中，则可所有桶的排序任务分散到 各个计算单元，完成后再进行结果合并。 图 12‑3 桶排序的并行计算 12.1.3 分治常见应用 一方面，分治可以用来解决许多经典算法问题。 ‧ 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后再找出跨越两 部分的最近点对。

那么，我们不禁发问：为什么分治可以提升算法效率，其底层逻辑是什么？换句话说，将大问题分解为多个 子问题、解决子问题、将子问题的解合并为原问题的解，这几步的效率为什么比直接解决原问题的效率更高？ 这个问题可以从操作数量和并行计算两方面来讨论。 1. 操作数量优化 以“冒泡排序”为例，其处理一个长度为 ? 的数组需要 ?(?2) 时间。假设我们按照图 12‑2 所示的方式，将 数组从中点处分为两个子数组，则划分需要 ?) 。 再思考，如果我们多设置几个划分点，将原数组平均划分为 ? 个子数组呢？这种情况与“桶排序”非常类似， 它非常适合排序海量数据，理论上时间复杂度可以达到 ?(? + ?) 。 2. 并行计算优化 我们知道，分治生成的子问题是相互独立的，因此通常可以并行解决。也就是说，分治不仅可以降低算法的 时间复杂度，还有利于操作系统的并行优化。 并行优化在多核或多处理器的环境中尤其有效，因为 源，从而显著减少总体的运行时间。 比如在图 12‑3 所示的“桶排序”中，我们将海量的数据平均分配到各个桶中，则可所有桶的排序任务分散到 各个计算单元，完成后再合并结果。 图 12‑3 桶排序的并行计算 12.1.3 分治常见应用 一方面，分治可以用来解决许多经典算法问题。 ‧ 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后找出跨越两部 分的最近点对。 ‧