【算法设计与分析】14 分治算法的一般描述和分析方法

女爷i 2023-08-17 16:25 138阅读 0赞

> 本文主要描述分治算法的一般描述和分析方法。衔接上一篇文章：[【算法设计与分析】13 分治策略的设计思想][13]

### 文章目录 ###

*   *  1 分治算法的一般性描述
     *   *  1.1 分支算法的时间分析
         *  1.2 两类常见的递推方程与求解方法
     *  2 总结

## 1 分治算法的一般性描述 ##

*  设分治算法为：Divide-and-Conquer§

![在这里插入图片描述][20190928152953539.png]

*  设计要点

1.  原问题可以划分或者规约为规模较小的子问题。其中子问题之间遵循以下的规则：
    
        1. 子问题与原问题具有相同的性质
         	2. 子问题的求解彼此独立
         	3. 划分时，子问题的规模尽可能均衡
2.  子问题较小时可以直接求解
3.  子问题的解综合可以得到原问题的解
4.  算法的实现：迭代或者递归

### 1.1 分支算法的时间分析 ###

时间复杂度函数的递推方程：

*   W ( n ) = W ( ∣ P 1 ∣ ) + W ( ∣ P 2 ∣ ) + . . . + W ( ∣ P k ∣ ) + f ( n ) W(n)=W(|P\_1|)+W(|P\_2|)+...+W(|P\_k|)+f(n) W(n)=W(∣P1∣)\+W(∣P2∣)\+...\+W(∣Pk∣)\+f(n)
 *   W ( c ) = C W(c)=C W(c)=C

其中

1.   P 1 , P 2 , . . . P k w 为 划 分 后 产 生 的 子 问 题 P\_1,P\_2,...P\_kw为划分后产生的子问题 P1,P2,...Pkw为划分后产生的子问题
2.   f ( n ) 为 划 分 子 问 题 以 及 将 子 问 题 的 解 综 合 得 到 原 问 题 的 解 的 总 工 足 量 f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量 f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量
3.  规模为c的最小子问题的工作两为：C

### 1.2 两类常见的递推方程与求解方法 ###

*   f ( n ) = ∑ i n a i f ( n − i ) + g ( n ) ， ( 1 ) f(n) = \\sum\_i^n a\_i f(n-i)+g(n)\{， (1)\} f(n)=i∑naif(n−i)\+g(n)，(1)
 *   f ( n ) = a f ( n b ) + d ( n ) ， ( 2 ) f(n)=af(\\frac\{n\}\{b\}) + d(n)\{， (2)\} f(n)=af(bn)\+d(n)，(2)

例子：

Hanoi塔， W ( n ) = 2 W ( n − 1 ) + 1 W(n)=2W(n-1)+1 W(n)=2W(n−1)\+1  
二分检索， W ( n ) = W ( n / 2 ) + 1 W(n)=W(n/2)+1 W(n)=W(n/2)\+1  
归并排序， W ( n ) = 2 W ( n / 2 ) + n − 1 W(n)=2W(n/2)+ n-1 W(n)=2W(n/2)\+n−1

那么这些递推方程如何求解？

*  方程1： f ( n ) = ∑ i n a i f ( n − i ) + g ( n ) f(n) = \\sum\_i^n a\_i f(n-i)+g(n) f(n)=∑inaif(n−i)\+g(n)

1.  迭代法、递归树

*  方程2： f ( n ) = a f ( n b ) + d ( n ) f(n)=af(\\frac\{n\}\{b\}) + d(n) f(n)=af(bn)\+d(n)

1.  迭代法、换元法、递归树、主定理

对于方程2，可以使用主定理，该定理可以很快求解出方程的解，前面的文章已经学习过主定理，这里再次提一下：

*  对于方程 T ( n ) = a T ( n / b ) + d ( n ) T(n)=aT(n/b)+d(n) T(n)=aT(n/b)\+d(n)

1.  如果d(n)为常数：

T ( n ) = \{ O ( n l o g b a ) , a ≠ 1 O ( l o g n ) , a=1 T(n)= \\begin\{cases\} O(n^\{log\_ba\}), & \\text \{$a \\not= 1$\} \\\\ O(logn), & \\text\{a=1\} \\end\{cases\} T(n)=\{ O(nlogba),O(logn),a=1a=1

1.  如果d(n) = c(n)

T ( n ) = \{ O ( n ) , a < b O ( n l o g n ) , a=b O ( n l o g b a ) , a>b T(n)= \\begin\{cases\} O(n), & \\text \{a < b\} \\\\ O(nlogn), & \\text\{a=b\} \\\\O(n^\{log\_b\{a\}\}), &\\text\{a>b\} \\end\{cases\} T(n)=⎩⎪⎨⎪⎧O(n),O(nlogn),O(nlogba),a < ba=ba>b

> 注：上述的 l o g b a log\_ba logba中的b是以b为底的意思，但是上面的公式显示的不明显。

## 2 总结 ##

*  想要彻底理解分治算法的思想，还需要多做练习，后面的文章会结合具体的例子，来讲解分治算法的思想在具体应用中的使用

[13]: https://lyy-0217.blog.csdn.net/article/details/101611795
[20190928152953539.png]: /images/20230810/bbdee7b143cd4210a73baeef6bd38b39.png