雅乐网

计算机技术、学习成长

计算机 » 算法 » 使用主定理求解递归式

使用主定理求解递归式

算法导论中的4.5节介绍了一个用于求解递归式的主定理,可以用来求解部分形如下面形式的递归式:

scrn20150402134024,其中a>=1 , b >1

描述的算法

把规模为n的问题分为a个子问题,每个子问题规模是n/b(原来的b分之一),分解子问题和合并子问题的时间是f(n)。

这样求解一个子问题需要时间T(n/b),求解所有子问题需要时间aT(n/b),再加上分解和合并的时间f(n),就得到了总的时间T(n)。

主定理的三种情况

算法导论中介绍的三种情况是这样的:

scrn20150402135229

这三个情况的表示可能会让有些人一头雾水,但是仔细研究后,可以直观的看出这三种情况是怎么分类的,而且使用起来并不麻烦。

其实这三种情况都是根据分解合并的函数 f(n) 和 scrn20150402135627的渐进大小关系来分的。注意是渐进意义上的大小,也就是多项式意义上的。所谓多项式意义,就是他们之间的差必须是n的几次方这种形式(比如n^2小于n^3,n^1.3 < n^1.4这种)。而如果相差logn这种形式就不是多项式意义上的,也不能应用主定理。

f(n) 和 scrn20150402135627 中的较大者决定了T(n)的大小。

情况一:

scrn20150402135627 渐进大于 f(n) ,这时候T(n) = θ(scrn20150402135627)

情况二:

f(n)和scrn20150402135627同阶,这时候T(n) = θ( scrn20150402135627  *  log n ) =  θ( f(n)  *  log n )

情况三:

f(n)多项式渐进大于scrn20150402135627,  T(n) =θ ( f(n) )

这时候还需要满足一个“正则条件”:存在c<1,af(n/b) < cf(n)。

主定理没有覆盖所有情况

如果情况一和三的渐进小于或大于不是多项式意义上的,而是logn之类的,就不能应用主定理。

还有,如果情况三不满足正则条件,也不能应用主定理。

例子

如果看了上面的三种情况还是摸不着头脑的话,没关系,看看下面的例子就好了。为了方便看a、b和f(n),再把主定理的形式贴一边。

scrn20150402134024

T(n) = 9T(n/3) + n

对比一下很容易得到 这个式子中: a = 9, b = 3, f(n) = n

那么我们来计算scrn20150402135627 ,等于 n^2

对比一下f(n)和scrn20150402135627,也就是n和n^2,显然n小于n^2,适用情况一。

得到解 T(n) = O (scrn20150402135627) =θ(n^2)

T(n) = T(2n/3) + 1

a = 1, b = 3/2 , f(n) = 1

scrn20150402135627 = n^0 = 1 ,和1是同阶的,适应情况二。

T(n) = O(scrn20150402135627 * logn) = θ(logn)

T(n) = 3T(n/4) + nlogn

a = 3, b = 4, f(n) = n*logn.

log(3,4)约等于0.793

scrn20150402135627 = n^0.793,虽然不准确,但是肯定小于n^1,和f(n)=nlogn进行比较,虽然f(n)包含logn的形式,但只看n的部分也至少要少了n^0.2 ,这个也是多项式意义上的,适用情况三。

使用情况三我们还需要验证正则条件

存在c<1,af(n/b) < cf(n)。把f(n)使用f(n) = nlogn代替

3* n/4 log(n/4) < c n logn

要想这个不等式成立,分别观察3/4n 和log(n/4)和右边对应的地方,显然右边的logn是大于左边的log(n/4)的,只要右边的cn 大于左边的3/4n 就可以了。

只要c大于3/4就可以,并且c<1 这样的c是存在的,至此可以应用情况3了

T(n) = θ (nlogn)

T(n)=2T(n/2)+nlogn

a = 2, b = 2, f(n) = nlogn

scrn20150402135627 = n 。我们注意到n确实是小于nlogn的,但是这并不是多项式意义上的小于,因为两个式子n的次数都是1,因此不能应用主定理。

这个递归式可以使用递归树进行求解。

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/master_theorem.html

上一篇:

下一篇:

我要评论

验证码*: 6 + 0 =