如何将以下问题解决为 f(n)=n! 据我所知，不适用于主定理的任何情况。T (n) = 16T (n/4) + n！
问问题
2089 次
1 回答
2
David Eisenstat 部分正确。情况 3 确实适用，但 T(n) = theta(n!)，而不是 O(n!)。
T(n) = 16T(n/4) + n！
主定理（AKA 主方法）的案例 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 AND af(n/b) <= cf(n) 对于大 n，T(n) 是 theta(n!)。
作为参考，请参阅此处的#10：http ://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
于 2019-11-27T04:18:10.690 回答