下面表达式的时间复杂度是多少?

Question

T(n) = 16T(n/4) + n!

我知道它可以用大师定理来解，但我不知道如何处理F (n) = n!

Answer 1

这是主定理的情形三。

自T(n) = 16T(n/4) + n!

f(n) = n!

a = 16, b = 4，故log_b a = log₄ 16 = 2。

主定理指出复杂度T(n) = Θ(f(n))如果C> log_b a where f(n) ∈ω;(n <一口> c> n^c对于n> n₀语句f(n) ∈ω;(n^c)为真。因此这个说法C> log_b a =2也成立。因此，对于索伦大师的第三种情况，复杂度T(n) = Θ(f(n)) = Θ(n!)。