主方法

2019-12-22 本文已影响0人 spraysss

$T(n)=aT(\frac n b)+f(n)$

如果 $\exists \epsilon>0,使得 f(n)=O {(n^{\log_ b ^{a-\epsilon}})}$ ，则 $T(n)=\Theta(n^{\log_ b^a})$
如果 $f(n)=\Theta(n^{\log_ b^a}),则T(n)=\Theta(n^{\log_ b^a}.\log n)$
如果 $\exists \epsilon>0$ ,使得 $f(n)=\Omega {(n^{\log_ b ^{a+\epsilon}})}$ ,且对于 $\forall c<1$ 与足够大的n，有 $af(\frac n b) \leq cf(n)$ ,则 $T(n)=\Theta(f(n))$

主方法可以简单记忆为 $f(n)$ 和 $n^{\log_ b ^{a}}$ 谁大取谁，相等的话需要乘上 $\log n$

上一篇下一篇

猜你喜欢

热点阅读