我该如何解决以下问题，因为 f(n)=n! 并不适用于主定理的任何情况。 T(n) = 16T(n/4) + n!
1个回答
2
David Eisenstat部分正确。第3种情况适用，但T(n) = theta(n!)，而不是O(n!)。
T(n) = 16T(n/4) + n!
Master定理（也称为Master Method）的第3种情况适用。a = 16，b = 4，f(n) = n!。n^(log [base(b)] a) = n^2。f(n)是n!。由于n!是omega(f(n))即n! omega n^2，并且af(n/b) <= cf(n)对于大的n成立，因此T(n)为theta(n!)。
参考资料：#10：http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
- Jay ARe
1
嘿@Jay，我们该如何证明af(n/b) <= cf(n)？ - Kumaravel Rajan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 7 主定理：当f(n)包含log的负指数时会出现问题。
- 3 Prove that f(n) = Θ(g(n)) iff g(n) = Θ(f(n))
- 6 主定理：为什么T(n)=16T(n/4)+n!被认为是Θ(n!)？
- 3 带有Log n重组的主定理
- 12 证明 f(n) + g(n) 是 O(max(f(n),g(n)))。
- 7 主定理中 f(n)=log n 的情况
- 3 如果f(n) = o(g(n)), 那么g(n) + f(n) = Θ(g(n))吗？
- 3 证明如果 g(n) 是 o(f(n)), 那么 f(n) + g(n) 是 Theta(f(n))。
- 4 如果f(n) = O(g(n))，g(n) = O(h(n))，其中f、g、h是函数，请证明f(n) = O(h(n))。
- 3 Iteration n * F(n - 1)+((n - 1) * F(n - 2))