分治算法

• 1.分治算法的核心思想

  • 分治算法是一种解决问题的通用方法，它将一个复杂的大问题分解成若干个规模较小、相互独立且与原问题形式相同的子问题，然后递归地解决这些子问题，最后将子问题的解合并，得到原问题的解。

• 2.分治三部曲

  • 分解:将原问题划分为相似的子问题。
  • 解决:递归地解决这些子问题，即对每个子问题调用分治算法自身。
  • 合并:将子问题的解合并成原问题的解

• 3.构造分治算法

  • 识别问题的分治结构
    • 首先，分析所要解决的问题，判断其是否具有分治结构。即问题能否被划分为若干个规模较小的、相互独立的子问题，且这些子问题与原问题具有相同的性质或形式。
    • 确保子问题之间没有重叠部分，且每个子问题的解不影响其他子问题的求解
  • 定义子问题
    • 明确如何将原问题划分为子问题。这包括确定划分的数量、划分的具体方式以及子问题的规模是如何随着递归深度减小的。
    • 描述子问题的形式和特征，确保它们与原问题在本质上是相同的，只是规模更小。
  • 设计递归求解策略
    • 确定递归的基本终止条件（基线条件），即问题规模小到一定程度时，可以直接求解而不必再进行分解。
    • 在递归函数内部，根据问题的分解方式，调用自身来处理每个子问题。通常，递归调用会伴随着参数的变化，反映出子问题的规模或范围。
  • 设计合并算法
    • 明确如何将子问题的解合并成原问题的解。这通常涉及到一个明确的、相对简单的合并操作或算法

• 4.递归与分治的关系

  • 递归是分治算法的核心实现手段：分治算法通常采用递归来解决分解得到的子问题。递归函数负责调用自身来处理子问题，直至达到基本终止条件。递归提供了简洁且易于理解的方式来表达问题规模的逐级减小和子问题的递归解决过程。
  • 分治算法为递归提供了框架和指导：分治算法为递归提供了明确的问题分解规则、递归终止条件和合并子问题结果的机制。递归在分治算法的框架下得以组织和控制，确保了递归调用的正确性和高效性。

• 5.分治算法的适用条件

  • 可分解性
    1. 问题规模可缩小：原问题应该能够被划分为若干个规模较小的子问题。
    2. 子问题结构相同：每个子问题应与原问题具有相同的本质特征和求解框架，只是规模上有所减小。
  • 子问题独立性
    1. 子问题间无交互：分解出的子问题之间相互独立，即解决一个子问题不需要依赖于其他子问题的解，也不会影响其他子问题的求解过程。
    2. 子问题解无副作用：子问题的求解过程中不会对其他子问题的数据产生副作用，确保合并阶段可以简单地将子问题解拼接起来。
  • 有穷子问题集
    1. 子问题数量有限：分解过程不会无限生成子问题，即存在一个递归深度，达到该深度后问题规模减小到可以直接求解的程度，形成递归的基本终止条件。
  • 子问题的合并性
    1. 存在明确的合并算法：对于子问题的解，应存在一个简单且高效的算法将它们合并成原问题的解。
    2. 合并操作与子问题数量无关或关联度低：合并子问题解的时间复杂度最好与子问题数量无关，或者只与问题规模呈较弱的关联。这样可以保证即使在问题规模较大时，合并阶段也不会成为算法的性能瓶颈。

• 6.分治算法的时间复杂度分析

  由于分治算法通常包含问题分解、递归求解子问题以及合并子问题解三个主要步骤，因此时间复杂度分析也围绕这三个方面展开。

  • 问题分解时间复杂度
    • 固定成本:分析将原问题划分为子问题所需的基本操作次数。这部分时间复杂度通常与问题规模无关，表现为常数阶（O(1)）或与问题规模呈较低阶的关联
    • 问题规模相关成本:某些情况下，问题分解可能涉及与问题规模相关的操作，如排序、搜索等。此时需要计算这些操作的时间复杂度，并考虑其对总时间复杂度的影响。
  • 递归求解子问题时间复杂度
    • 递归方程:假设递归函数的时间复杂度为 T(n)，其中 n 表示问题规模。根据递归函数的定义，写出递归方程来描述 T(n) 与子问题规模 n/b（其中 b 是每次划分后子问题的规模比例）之间的关系。
    • 基本情况:确定递归的基本终止条件，即问题规模小到一定程度时，可以直接求解的基线情况。基线情况的时间复杂度通常为常数阶（O(1)）或与问题规模呈较低阶的关联。
  • 合并子问题时间复杂度
    • 合并算法:分析合并子问题解所需的基本操作次数。这通常与子问题的数量或子问题规模有关，但合并操作相对于子问题求解通常较为简单，时间复杂度较低。
    • 合并次数:考虑合并操作发生的次数，通常与递归调用的层数或子问题数量相关。
  • 总复杂度
    • 对于大多数分治算法，递归求解子问题的时间复杂度占主导地位。可以利用主定理（Master Theorem）或递归树方法求解递归方程，得到递归求解子问题的渐近时间复杂度。

• 7.典型的分治算法

  • 快速排序
    • 分治递归过程
      1. 划分:选取一个基准元素（pivot），通过一趟排序将待排序数组划分为两部分，使得左侧所有元素都不大于基准，右侧所有元素都不小于基准。
      2. 递归:分别对左右两个子数组进行快速排序。
      3. 合并:无需额外操作，因为子数组已经是有序的，递归返回后整个数组即为有序。
    • 终止条件
      • 当子数组长度为1或0时，认为数组已经有序，无需继续递归。即当处理的子数组只剩下一个元素或者为空时，递归结束。
  • 归并排序
    • 分治递归过程
      1. 划分:将待排序数组均匀地分为两个子数组。
      2. 递归:对两个子数组分别进行归并排序。
      3. 合并:在每次的递归中,创建一个临时数组，从左到右依次比较两个已排序子数组中的元素，将较小者放入临时数组，直到其中一个子数组的所有元素都被取完，然后将另一个子数组剩余的元素直接复制到临时数组相应位置。最后将临时数组的内容复制回原数组,这个数组是上层递归的数组序列的左侧或右侧序列,以此类推,再次向上返回数组,直到数组中的元素全部有序.
    • 终止条件:当待排序数组的长度为1时，认为数组已经有序，无需继续递归。即当处理的子数组只剩下一个元素时，递归结束。
  • 二分查找
    • 分治递归过程
      1. 划分:在一个有序数组中，取中间元素作为基准，将数组划分为左右两半。
      2. 递归:根据目标值与中间元素的大小关系，决定在左半部分还是右半部分继续进行二分查找。
      3. 合并:二分查找过程中无需合并操作，直接返回查找到的目标元素的索引或表明未找到的结果。
    • 终止条件:待查找区间缩小到只剩一个元素时，检查这个元素是否为目标值。如果是，则查找成功，返回其索引；若不是且两侧区间均为空（即目标值不在数组中），则查找失败，返回特定标识（如 -1 或 null）。
  • 汉诺塔问题
    • 分治递归过程
      1. 划分:将所有盘子（除了最底层的一个）视为一个整体，看作一个新的子问题
      2. 递归:将除最底层盘子外的所有盘子借助第三根柱子移动到第二根柱子上。
      3. 合并:将最底层的盘子直接移动到目标柱子（第二根柱子或第三根柱子）上。
    • 终止条件:当待移动的盘子数量为1时，直接将该盘子从起始柱子移动到目标柱子，无需进一步递归。即当问题规模减小到只剩一个盘子时，递归结束。