主定理(Master Theorem)与时间复杂度

1. 问题

Karatsuba 大整数的快速乘积算法的运行时间(时间复杂度的递推关系式)为 T(n)=O(n)+4⋅T(n/2),求其最终的时间复杂度。

2. 主定理的内容

主定理(Master Theorem)与时间复杂度

3. 分析

所以根据主定理的判别方法,可知对于 T(n)=O(n)+4⋅T(n/2),a=4,b=2,则 f(n)=O(n)<nlogab=2,符合第一个判别式,因此,T(n)=O(n2)

上一篇:闭区间套定理(Nested intervals theorem)讲解2


下一篇:华东师范大学p163页,用闭区间套定理证明数列的可惜收敛准则,被网友解决了。