分治算法学习笔记

1、分治算法的设计思想：

分治法的设计思想，大事化小，名个击破，分而治之。 将难以直接解决的大问题，分割成一些规模较小的子问题， 子问题相互独立并与原问题相同，以便各个击破，分为治之。

2、分治算法的基本思想

  • 分解为子问题
  • 求解子问题
  • 合并得到原问题的解

3、分治法的适用条件

4、分治算法的改进方法

  • 减少子问题的个数

  • 改进分治的均衡度

  • 减少合并的时间

5、分治算法选择题

解析：

在分治法中，通常我们说的“相同”指的是解决问题的方法或过程是相同的，而不一定是子问题在所有方面都完全相同。

例如，在归并排序中，我们将数组分成两半进行排序，这两半的排序过程是相同的，但它们可能包含不同的元素。

6、分治算法的三个过程

  • 划分

  • 递归地求解

  • 合并

7、分治算法时间复杂度分析的方法

可以用递归树来分析分治算法的时间复杂度。

8、分治法是将一个难以直接求解的复杂问题分解成若干个规模较小、 相互独立且类型相同的子问题，然后求解这些子问题， 直到子问题足够小能够直接求解，再将子问题的解组合成原始问题的完整答案。