master theorem

run_away · 2024-09-19 21:34:38 · 算法·理论

若给出一算法的渐进递归式为

我们需要求出一个关于 n 的多项式来表示它的时间复杂度。

大部分的式子肯定不能直接递归进去解，有一个非常强大的定理专门解决这样的问题，叫做 master theorem，就是大师主定理。

设 c_{crit}=\log_b a，且存在 c 满足 f(n)=O(n^c)，那么可以分成 3 种情况：

• c>c_{crit}$，则 $T(n)=O(n^c)
• c=c_{crit}$，则 $T(n)=O(n^c\log n)
• c<c_{crit}$，则 $T(n)=O(n^{c_{crit}})

另外，其中的第二条还有一种拓展：若 f(n)=O(n^{c_{crit}}\log^k n)，其中 k\ge 1 且是一个常数，则有 T(n)=O(n^{c_{crit}}\log^{k+1}n)（第二条实际上就是 k=0 时的特殊情况）

e.g.