分治算法概念

  分治算法的设计思想是，将一个难以直接诶解决的大问题，分割成一些规模较小的相同的问题，以便各个击破，分而治之。

  对于一个规模为n的问题，若该问题可以容易地解决（如规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地求解这些问题，然后将各个子问题的解合并得到原问题的解。这种算法设计策略就是分治算法，简称分治法。

  如果原问题可以分割成k个子问题，1<k<=n,且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复利用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

  分治法基本步骤：

1）把一个大问题分成多个小问题

    2）分别解决每个小问题

    3）把每个小问题的解组合起来。

  分治算法应用广泛，例如排序算法（归并排序，快速排序），树分治（点分治，边分治），快速傅里叶变换，

Strassen矩阵乘法等

题目推荐：个人分类