分治算法 —— 算法总结

分治算法 —— 总结

时间总是太快啦！我将近花费四天左右的时间来学习分治算法。总体上把大部分分治算法的经典例题都做啦，接近两天的时间完成分治法相关的博客撰写来记录题目心得与体会！

今天来对分治算法总结一下！！！

虽然分治算法的相关例题做的也不多也不少，但我仍旧不敢说我对分治算法了如指掌，胸有成竹啦！顶多算是入门啦吧！路漫漫其修远兮，吾将上下而求索！

此处附上分治算法经典例题，来源以及题解。

（1）棋盘覆盖 来源 题解

（2）循环赛日程表 来源 题解

（3）快速排序 题解

（4）合并排序 题解

（5）最大子序列和 来源 题解

（6）逆序对个数 来源 题解

（7）光荣的梦想 来源 题解

（8）黑白棋子的移动 来源 题解

（9）快速幂 题解

（10）取余运算 来源 题解

（11）麦森数 来源 题解

分治算法 ; 一般大规模问题化为小规模问题，最后由小规模问题的解合并得到大规模的解

（说明：有时候是不需要合并的，依题而定）

1. 二维平面的划分(一分为四 或 一分为一)

棋盘覆盖将一个二维平面划分为四个子问题，每一个子问题又可以接着划分为四个子问题直到划分到递归的边界

循环比赛日常表虽不是划分为四个子问题，由于其中的一个子问题与另三个子问题有紧密的关系。故可以将一个二维平面划分为1个子问题，划分后的子问题又可以继续递归划分一个子问题直到划分到递归边界

2.一维平面的划分（归并排序和快速排序）

归并排序和快速排序都是将一个一维平面的问题划分为两个子问题，每一个子问题接着继续划分为两个子问题直到划分到元素的个数为一

3.归并排序之最大连续子序列和

合并排序的最经典的用法，最大子序和的最大值要门出现在左右part和中间part三者之间，需要做的是如何求中间part，其他部分和归并排序一模一样,最后来个三者比较即可

4.归并排序的应用 (逆序对个数 与 光荣的梦想)

逆序对个数和光荣的梦想其直接的思想是冒泡排序来记录交换的次数，但是冒泡排序的效率较低。因此通常采取归并排序的策略来记录交换的次数

5.空间上一分为一划分（黑白棋子的移动）

黑白棋子的移动属 n规模的问题划分为n-1规模问题直到划分到n = 4的情况

6.空间上的一分为二划分(快速幂)

快速幂采用分治的策略，a ^ b 直接拆成 a ^(b/2) * a^(b/2) * a ^ (b %2). a^(b/2) 继续划分，不断在空间上不断的分两半往下一层递进

7.快速幂应用 （取余运算 和 麦森数）

取余运算主要在快速幂的计算过程中不断取余，而不是用快速幂计算完再求余

麦森数主要使用快速幂，不过此时的快速幂的类型不是整型数据而是自定义的大整数类型，额外涉及一些数论的相关知识

结语

分治算法 分治算法的核心就是分而治之,也就是将原问题划分为若干个规模更小但结构与原问题相似的子问题,递归地解决这些子问题然后进行合并,就可以得到原问题的解。

分治算法是一种算法策略，可以递归实现也可以非递归实现。但大部分是需要递归来实现的，因为递归本身就是一种分的体现呀！！！

分治算法

1. 在二维上 划分四个子问题，两个子问题或一个子问题(如棋盘覆盖，循环比赛日程表)
2. 在一维上 划分为两个子问题(左右两个part，如递归排序和快速排序)
3. 在空间上 划分为一个子问题，层层递进(如 黑白棋子移动)
4. 在空间上 划分为两个子问题，层层递进(如 快速幂)

以上都是4天分治经典题目学习与2天博客撰写的个人经验总结！大佬勿喷