math - 解决递归

Question

T(n)=T(n-1) + lgn 我的做法是：

代入 n-1,n-2,n-3 最后我们得到 T(n)=T(1) + lg 2 +lg 3 所以 lg n => T(n) = lg(2*3*4* 5 n) 因此 T(n)=lg(n!)。

但他们给出的答案是 nlgn。

Answer 1

这是计算复杂性的问题吗？如果是这样，那么你和“他们”都是正确的。

O(lg(n!)) = O(lg(n^n)) = O(n lg(n))

更严格地说，来自斯特林公式：

lg(n!) = n lg(n) - n + O(ln(n))

所以

O(lg(n!)) = O(n lg(n)) + O(n) + O(ln(n)) = O(n lg(n))