algorithm - N 次幂 n i-e n^n 是否是多项式？ n^2 和 n^n 之间是否存在多项式差异？

Question

n 的 n 次方(即 n^n)是多项式吗？ T(n) = 2T(n/2) + n^n 可以用master方法求解吗？

Answer 1

它不仅不是多项式，而且比阶乘还差。 O(n^n) 支配 O(n!)。同样在masters方法中f(n)必须是多项式的，所以你不能使用它。