T(n) = 16T(n/4) + n!
我知道可以用Master theorem解决,但是我不知道怎么处理 f(n) = n!
最佳答案
这是 Master Theorem 的案例三。
因为 T(n) = 16T(n/4) + n!
这里 f(n) = n!。
a = 16 和 b = 4,所以 logb a = log4 16 = 2。
主定理指出复杂度 T(n) = Θ(f(n)) 如果 c > logb a 其中 f(n) ∈ Ω(nc) 。 由于 f(n) = n! > nc 对于 n > n0 的某个值,语句 f(n) ∈ Ω (nc) 为真。因此声明 c > logb a =2 也成立。因此,根据 Thoerem 大师的第三个案例,复杂性 T(n) = Θ(f(n)) = Θ(n!)。
关于algorithm - 以下表达式的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40415949/