主定理
所谓主定理，就是用来解递归方程的一种方法，此方法可以用来求解大多数递归方程。
设递归方程为T(n)=aT(n/b)+f(n) （其中a≥1，b＞1）
主定理：
1. 如果存在常数ε＞0有f(n)=O(n^(logb^a-ε)),则T(n)=Θ(n^(logb^a))；
2. 若f(n)=Θ(n^(logb^a))，则T(n)=Θ(n^(logb^a)logn2^n)；
3. 若对某个常数ε＞0有f(n)=Ω(n^(logb^a)+ε)，且对某个常数c＜1和所有足够大的n有af(n/b)≤cf(n)，则T(n)=Θ(f(n))。
歪曲记忆法：谁大听谁的，相等就乘个对数系数
多项式大于（小于）
在看算法导论时候，看到讲主定理节时，有“在第一种情况中，不仅要有f(n)小于n^log(b)(a)，还必须是多项式地小于……”，之前先入为主的以为多项式地小于就是两者之差为一个多项式（事实上这么想也没大错，只是形式不对），但注意到是在算法的世界里，所以不需要精确到一个多项式（形如n^3+n^2+n+3之类的），只要两者之比（即f(n)/log(a)(b)）渐近小于n^e(e > 0)即可。
归纳起来，就是：（e > 0的任意实数）
f(x) > g(x) * n^e ==> f(x)多项式地大于g(x)；
f(x) < g(x) * n^e ==> f(x)多项式地小于g(x)。
歪曲记忆法：就是得差个多项式啊，多项式是n、n^2、n^3……这种样子的，lgn 不是个合法多项式
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227361.html原文链接：https://javaforall.net
