洛阳外贸网站推广,wordpress主题 贴吧,如果熊掌号做的不好会不会影响网站,淘宝网站建设需求分析本文主要描述分治算法的一般描述和分析方法。衔接上一篇文章#xff1a;【算法设计与分析】13 分治策略的设计思想 文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结1 分治算法的一般性描述
设分治算法为#xff1a;Divide-and… 本文主要描述分治算法的一般描述和分析方法。衔接上一篇文章【算法设计与分析】13 分治策略的设计思想 文章目录1 分治算法的一般性描述1.1 分支算法的时间分析1.2 两类常见的递推方程与求解方法2 总结1 分治算法的一般性描述
设分治算法为Divide-and-Conquer§ 设计要点 原问题可以划分或者规约为规模较小的子问题。其中子问题之间遵循以下的规则 1. 子问题与原问题具有相同的性质2. 子问题的求解彼此独立3. 划分时子问题的规模尽可能均衡子问题较小时可以直接求解 子问题的解综合可以得到原问题的解 算法的实现迭代或者递归
1.1 分支算法的时间分析
时间复杂度函数的递推方程
W(n)W(∣P1∣)W(∣P2∣)...W(∣Pk∣)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)CW(c)CW(c)C
其中
P1,P2,...Pkw为划分后产生的子问题P_1,P_2,...P_kw为划分后产生的子问题P1,P2,...Pkw为划分后产生的子问题f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量f(n)为划分子问题以及将子问题的解综合得到原问题的解的总工足量规模为c的最小子问题的工作两为C
1.2 两类常见的递推方程与求解方法
f(n)∑inaif(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)af(nb)d(n)(2)f(n)af(\frac{n}{b}) d(n){ (2)}f(n)af(bn)d(n)(2)
例子
Hanoi塔W(n)2W(n−1)1W(n)2W(n-1)1W(n)2W(n−1)1 二分检索W(n)W(n/2)1W(n)W(n/2)1W(n)W(n/2)1 归并排序W(n)2W(n/2)n−1W(n)2W(n/2) n-1W(n)2W(n/2)n−1
那么这些递推方程如何求解
方程1f(n)∑inaif(n−i)g(n)f(n) \sum_i^n a_i f(n-i)g(n)f(n)∑inaif(n−i)g(n)
迭代法、递归树
方程2f(n)af(nb)d(n)f(n)af(\frac{n}{b}) d(n)f(n)af(bn)d(n)
迭代法、换元法、递归树、主定理
对于方程2可以使用主定理该定理可以很快求解出方程的解前面的文章已经学习过主定理这里再次提一下
对于方程T(n)aT(n/b)d(n)T(n)aT(n/b)d(n)T(n)aT(n/b)d(n)
如果d(n)为常数
T(n){O(nlogba),a̸1O(logn),a1T(n) \begin{cases} O(n^{log_ba}), \text {$a \not 1$} \\ O(logn), \text{a1} \end{cases} T(n){O(nlogba),O(logn),a1a1
如果d(n) c(n)
T(n){O(n),a bO(nlogn),abO(nlogba),abT(n) \begin{cases} O(n), \text {a b} \\ O(nlogn), \text{ab} \\O(n^{log_b{a}}), \text{ab} \end{cases} T(n)⎩⎪⎨⎪⎧O(n),O(nlogn),O(nlogba),a babab 注上述的logbalog_balogba中的b是以b为底的意思但是上面的公式显示的不明显。 2 总结
想要彻底理解分治算法的思想还需要多做练习后面的文章会结合具体的例子来讲解分治算法的思想在具体应用中的使用
