流离之人追逐幻影

用户名：pwj666

访问量：60215

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

分治法-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-06-24 00:15:00 浏览：845　|　评论：0　

**分治法**
定义：
```
将一个难以直接解决的大问题，分割成一些规模较小的与原问题形式相同的子问题，用递归解决这些子问题，然后将子问题的解合并即为原问题的解。
```
分治法在每一层递归上都有三个步骤： 
```
1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

3）合并：将各个子问题的解合并为原问题的解。
```
分治算法的适用条件：
```
分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质

3) 利用该问题分解出的子问题的解可以合并为该问题的解

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题

```
适用条件分析：
```
1）第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

2）第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

3）第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

4）第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

```
时间复杂度：
```
例如：一个规模为n的问题，每次将其分解为k个子问题，直至子问题的规模为1,合并k个子问题的时间复杂度为O(n).
则原问题的时间复杂度T(n)=kT(n/k)+O(n).由此可求得起时间复杂度为 O（nlogn）.
```
![](/image_editor_upload/20190624120529_93791.png)
由于logk为常数，所以可以忽略。则它的时间复杂度为O（n log n).

补充：
```
1）从严格的定义上讲，一般把子问题个数为1的情况称为 减治，大于1的情况称为 分治，通常情况下不必在意这种区别。（例如n!的求解过程就是减治，Fibonacci数列的求解过程就是分治）

2）分治法作为一种算法思想，既可以用递归的手段去实现，也可以通过非递归的手段去解决，视具体情况而定。
```
可使用分治法解决的一些经典问题

```
1）二分搜索
2）大整数乘法
3）Strassen矩阵乘法
4）棋盘覆盖
5）合并排序
6）快速排序
7）线性时间选择
8）最接近点对问题
9）循环赛日程表
10）汉诺塔 
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

弟弟的作业（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

分治法-----每日PAT

评论区

精彩推荐

C语言训练-大、小写问题（C语言代码）

时间转换（Java代码）

计算质因子（C++代码）

字符串比较（C语言代码）答案错误？？？？

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

WU-拆分位数（C++代码）

【金明的预算方案】（C++代码）

【计算球体积】（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

弟弟的作业 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

分治法-----每日PAT

评论区

精彩推荐

C语言训练-大、小写问题 （C语言代码）

时间转换 （Java代码）

计算质因子 （C++代码）

字符串比较 （C语言代码）答案错误？？？？

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

WU-拆分位数 （C++代码）

【金明的预算方案】 （C++代码）

【计算球体积】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

弟弟的作业（C语言代码）

　　评论区

C语言训练-大、小写问题（C语言代码）

时间转换（Java代码）

计算质因子（C++代码）

字符串比较（C语言代码）答案错误？？？？

WU-拆分位数（C++代码）

【金明的预算方案】（C++代码）

【计算球体积】（C语言代码）