math - 如何解决 T(n+1)=T(n)+logn 的复杂度

Question

所以我有这个递归：

T(1)=a, n=1
T(n+1)=T(n)+logn, n>=1

当我通过替换解决时，我得到这个表达式：

T(n)=log(n-1)...+log(n-k)+T(n-k)

（K 为 n-1）

然后，

T(n)=log(n-1)...+log(1)+T(1)

log(1)=0 和 T(1)=a

从那里，我不知道如何获得复杂度为 O(n^2) 的表达式 [这是练习中需要的]

谁能帮我？

谢谢

标签： mathtime-complexity

Answer 1

如你所见T(n) = log(n!)。您可以使用斯特林公式并替换n!为(n/e)^n * \sqrt{2\pi n}。因此，您将获得T(n) ~ n log(n/e) + 0.5 log(2 pi * n) = Theta(n log(n)).