分治算法主定理的计算和推倒笔记 | 您所在的位置:网站首页 › 算法分析递推式 › 分治算法主定理的计算和推倒笔记 |
分治算法主定理的计算和推倒笔记
在学习分治的时候,通常都会遇到通用分治算法递推式: 其中 T(n)代表了分治算法的时间复杂度,n代表了问题的输入规模,a和b分别代表n个输入实例划分为b个子问题,其中a个需要被处理;最后f(n)代表最后合并处理后的结果所需要的时间复杂度。显而易见,T(n)的增长次数取决于a,b已经f(n)。通常会直接给出如下的主定理来描述T(n): 其实对于这个公式所表示的意思,我不是很明白。比如我当时就有几个问题: f(n) 为什么是属于n的d次方的复杂度? 三个等式是怎么算出来的,成立条件表示的是什么意思?为了解决我的疑惑,查阅了不少的资料,也想明白了问题。因此特此在本文中记录下。 第一个问题 - f(n) 为什么是属于n的d次方的复杂度?对于这个问题我的理解是,对于划分的b个子问题,不管是否需要处理最后都需要合并。那么合并这些子问题的结构,至少是O(n)的复杂度。如果复杂一点还有可能是O(n ^ 2)这样子(比如2个结果集,还要在排序下,然后又使用了O(n ^ 2)的算法) 第二个问题 - 主定理如何计算出来的?主定理的计算有着两种方法:递推求解法和递归树求解法。对于递归求解法,要求较高的数学方法而且比较抽象(简单的来说就是我不懂哈哈哈),所以不打算记录下。这里主要谈谈我对递归树求解法的理解。通过递归树可以把T(n)的各个递归的部分画出来。 递归的最后规模是1,因此可以得出如下的几个结论: 递归树的高度成本和(表示了合并所有结果的成本): 这里解释下a/b^d 这个部分是怎么来的。如下的推倒,当把T(n/b)替换之后,则可得到a/b^d 这个部分。(原本b^d是在O()中,因为算是常数项,所以可以提出来) 来看下两个比较重要的部分: a.第一层的成本是: b. 最后一层的成本是: 根据上面的递归树图,我们可以知道时间复杂度 = 成本和,所以会出现以下这三种情况: 如果a/b^d < 1 既每一层的成本和都是递减的,则时间复杂度可以按第一层计算,既T(n) = O(n^d) 如果a/b^d = 1 既每一层的成本和是一样的,那么总成本就是把第一层的成本乘以树高,既:所以可以通过a/b^d 和1的关系,可以得出不同的时间复杂度度。也就最后得到了这个公式: 1.分治法(一). https://www.cnblogs.com/jmzz/archive/2011/06/10/2077923.html. 2.分治法时间复杂度求解秘籍. https://www.cnblogs.com/jmzz/archive/2011/06/10/2077923.html. |
CopyRight 2018-2019 实验室设备网 版权所有 |