【算法设计与分析】分治法

0.分治法的思想

是将大问题拆成很多个小问题，然后将小问题的答案处理得到大问题的答案。

父问题拆解的子问题和父问题有相同之处，比如，图分解之后还是图，数组分解之后还是数组，

同时，子问题的解组合在一起，能够得到父问题的解，比如排序算法，小区域的排序之后合并可以得到原问题的排序。

1.问题排序

   1>首先，先考虑用什么存储结构

   2>考虑边界的情况，比如空、1、2个的情况。

   3>分析时间复杂度是确认执行次数最多的元操作，计算它的次数。考虑最好、最坏、平均情况。

   3>目前已学过的算法

        冒泡法：以递增为例，以此和下一个数相比较，进行相邻位置的移动，这样一次遍历之后就会得到当前最大的元素，并把其放置到相应的位置，0（n^2)

        选择排序：以递增为例，先遍历得到最大的，元素，然后把它放到自己对应的位置上，0（n^2)

        插入排序：以递增为例，从第二个元素开始，每次都认为前面的数已经排好序（事实上也是），然后把当前的数插入进去即可。0（n^2)

   4>利用分治思想的排序

       4.1合并排序：先把数组分成几个小数组，然后做好数组内的排序，再把它们以此比较合在一起。

参考博客:https://blog.csdn.net/GentleCP/article/details/101108413?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

 在计算时间复杂度的时候，其实类似递归。

    4.2 快速排序

        合并排序是从元素的位置上分治，而快速排序是从元素的值上分治。

        选择一个数之后，让小于这个数的值的数都移动到这个数的左边，而大于它的数都移动到它的右边。

       当然，实现这个算法需要使用一些技巧，如果我们直接取这个数不断移动未免太低效，设计两个指针，分别从队头和队尾进行遍历，一旦左边的指针发现数比选定的数大，而右边的数发现选定的数比左边的数小，那我们就把它们交换位置。

 （图源啊哈算法）

参考博客：https://blog.csdn.net/starlet_kiss/article/details/86010904

（图源见水印）

当一次基准数归位之后，接下来仍然是使用分治法，左边的数拆成一个数组，右边的数拆成一个数组，重复以上步骤。

 然后再把它们组合在一起变成新的排好序的数组。

平均时间复杂度是0(nlogn),最差是0(n^2)

所以我们明白，一个算法之所以能够快，是因为它的比较和移动的次数比暴力法少，快速排序每次交换都是跳跃式的。

2. 分治思想在二叉树中的应用

 显然，二叉树的定义上就有分治的思想。

要注意，在这里，加法运算并不是执行最频繁的操作，应该是检查树是否为空。

原文：https://www.cnblogs.com/SeasonBubble/p/12467266.html