算法学习之求解递归式~主定理

算法学习之求解递归式~主定理

文章目录

算法学习之求解递归式~主定理 一、主定理定义 二、主定理应用 三、参考文献

一、主定理定义

令a>=1和b>1是常数，f(n) 是一个函数，T(n) 是定义在非负整数上的递归式：$$T(n)=aT(n/b)+f(n)$$其中我们将n/b解释为 $$\lfloor n/b\rfloor 或\lceil n/b\rceil$$那么T(n) 有如下渐进界：$$1.若对某个常数\epsilon >0,有f(n)=O(n^{\log b^{a-\epsilon }});$$ $$则T(n)=\Theta (n^{\log b^a})$$ $$2.若有f(n)=\Theta (n^{\log b^a});则T(n)=\Theta (n^{\log b^a}\lg n)$$ $$3.若对某个常数\epsilon >0,有f(n)=\Omega (n^{\log b^{a+\epsilon }})$$ $$且对某个常数c<1和所有足够大的n有af(n/b)<=cf(n),$$ $$则T(n)=\Theta (f(n))$$

在使用主定理之前，我们来理解一下它的含义。对于三种情况中的每一种，我们将函数f(n) 与函数 n^(log b^a) 进行比较。两个函数较大者决定了递归式的解。对于情况一：若f(n) 渐进小于函数 n^(log b^a) ，要相差一个因子n^ε ，其中ε 是大于0的常数。对于情况三：除了要满足条件f(n) 渐进大于函数 n^(log b^a) ，还要满足“正则”条件af(n/b)<=cf(n) .

二、主定理应用

例子：已知一个算法运行时间的递归式为：$$T(n)=2T(n/2)+\Theta (n)$$;根据主定理，求出递归式的解。 解： 由主定理可知：a=2, b=2, f(n)=Θ(n)$$n^{\log b^a}=n^{\log 2^2}=n$$ $$f(n)=\Theta (n)=\Theta (n^{\log 2^2})=\Theta (n^{\log b^a})$$满足主定理第2种情况，所以递归式的解为$$T(n)=\Theta (n^{\log b^a}\lg n)=\Theta (n^{\log 2^2}\lg n)=\Theta (n\lg n)$$

三、参考文献

以上内容出自《算法导论》