【算法设计与分析】13 分治策略的设计思想

超、凢脫俗 2023-08-17 16:22 55阅读 0赞

> 算法中很多方法都是可以采用分治策略进行设计与优化，那么什么是分治策略？如何使用分治策略进行算法的设计与分析？

### 文章目录 ###

*   *  1. 分治策略的基本思想
     *   *  1.1 二分检索的设计思想
         *  1.2 二分归并排序的设计思想
         *  1.3 Hanoi塔的递归算法
     *  2 小结

## 1. 分治策略的基本思想 ##

*  分治策略（Divide and Conquer）

1.  将原始问题划分或归结为规模较小的子问题
2.  递归或者迭代的求解每个子问题
3.  将子问题的解综合得到原问题的解

在设计分治策略时，一定要注意以下几点：

1.  子问题与原问题的性质完全一样
2.  子问题之间可以彼此独立的求解
3.  递归停止时，子问题可以直接进行求解得出结果。

下面以二分检索的例子来分析分之策略的思想。

### 1.1 二分检索的设计思想 ###

*  设算法：Binary Search(T，l，r，x)。
 *  输入：排好序的数组T ，下标从l到r；数x。
 *  输出：j //若x在T中，则为下标，否则为0

给出下面的伪码

![在这里插入图片描述][20190928141010801.png]  
二分检索的设计思想：

1.  通过x与数组的中位数进行比较，将原问题归结为规模减半的子问题。如果x小于中位数，则子问题由小于x的数构成，否则子问题由大于x的数构成。
2.  对子问题进行二分搜索算法
3.  当子问题为1时，直接比较T\[m\]与x，若相等则返回m，否则返回0.

二分检索最坏情况下时间复杂度分析，在前面的文章中已经学习了如何分析算法的时间复杂度，如果不懂下面的公式的，可以多看看前面的文章。

W ( n ) = W ( ⌊ n / 2 ⌋ ) + 1 W(n)= W(\\lfloor n/2 \\rfloor)+1 W(n)=W(⌊n/2⌋)\+1  
 W ( 1 ) = 1 W(1) = 1 W(1)=1

可以解出：

W ( n ) = ⌊ l o g n ⌋ + 1 W(n) = \\lfloor logn \\rfloor +1 W(n)=⌊logn⌋\+1

### 1.2 二分归并排序的设计思想 ###

*  设算法：Merge Sort(A,p,r)
 *  输入：A\[p…r\]
 *  输出：元素按从小到大排序额数组A

先看以下伪码：

![在这里插入图片描述][20190928143010503.png]  
二分归并的设计思想：

1.  将原问题划分为规模为n/2的两个子问题
2.  继续划分，将原问题归结为4个子问题，继续…当子问题估摸为1时，划分结束。
3.  从规模1到n/2，陆续归并被排好序的两个数组。每归并一次，数组规模扩大一倍，直到原始数组。

二分归并排序的时间复杂度：假设n为2的幂次方，二分归并排序最坏时间复杂度为：

W ( n ) = 2 W ( n / 2 ) + n − 1 W(n) = 2W(n/2) + n-1 W(n)=2W(n/2)\+n−1  
 W ( 1 ) = 0 W(1) = 0 W(1)=0

可以解出：  
 W ( n ) = n l o g n − n + 1 W(n) = nlogn - n + 1 W(n)=nlogn−n\+1

> 仔细体会着其中的分治策略

### 1.3 Hanoi塔的递归算法 ###

![在这里插入图片描述][20190928144139944.png]  
Hanoi塔的算法设计思想：

1.  将原问题归结为规模为n-1的两个子问题
2.  继续归结，将原问题归结为n-2的四个子问题.继续… ，当子问题规模为1时，归约过程截止。
3.  从规模为1到n-1，陆续组合两个子问题的解，知道规模为n。

## 2 小结 ##

1.  将原问题归约为规模较小的子问题，**子问题与原问题性质完全一样**
2.  子问题规模足够小时，可以直接求解
3.  算法可以递归也可以迭代实现
4.  算法的分析方法为：递推方程

[20190928141010801.png]: /images/20230810/995995b653f842c9afda5c130b902199.png
[20190928143010503.png]: /images/20230810/88a9f639a6c1489c92426a0a7a765a0b.png
[20190928144139944.png]: /images/20230810/a5917045b3184841a4fa3eb31bb6d039.png

【算法设计与分析】13 分治策略的设计思想

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 3.算法设计与分析__分治法

相关 2.算法设计与分析__递归与分治策略

相关【算法设计与分析】13 分治策略的设计思想

相关算法设计与分析——递归与分治策略——快速排序

相关算法设计与分析——递归与分治策略——棋盘覆盖

相关算法设计与分析——分治与递归策略——hanoi问题

相关算法设计与分析——递归与分治策略——全排列

相关算法设计与分析——算法思想总结

相关递归与分治策略（一）---算法设计与分析

相关算法设计与分析实验一分治算法