计算递推关系 T(n)=T(n-1)+logn

Question

我们要通过重复替换来解决递推关系：

T(n)=T(n-1)+logn

我开始替换并得到以下结果。

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

根据对数乘积法则，log(mn)=logm+logn,

T(n)=T(n-2)+log[n*(n-1)]

继续这个，我明白了

T(n)=T(n-k)+log[n*(n-1)*...*(n-k)]

我们知道基本情况是 T(1)，所以 n-1=k -> k=n+1，并将其代入我们得到

T(n)=T(1)+log[n*(n-1)*...*1]

显然 n*(n-1)*...*1 = n！所以，

T(n)=T(1)+log(n!)

超出这一点我不知道如何解决。答案只是O(log(n!))吗？我读过其他解释，说它是 θ(nlogn)，因此 O(nlogn) 和 Ω(nlogn) 分别是上限和下限。

Answer 1

这扩展到 log (n!)。你可以看到这个，因为

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

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

= T(n - 3) + log (n - 2) + log (n - 1) + log n

= ...

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

= T(0) + log n！

确切的答案取决于 T(0) 是什么，但对于 T(0) 的任何固定常数值来说，这是 θ(log n!)。

注释 - 使用斯特林近似法，θ(log n!) = θ(n log n)。这可能会帮助您将其与现有的复杂性类别联系起来。

希望这有帮助！

Answer 2

不需要斯特林公式即可获得大 Theta 边界。它的复杂度为 O(n log n)，因为它是最多 n 项的总和，每项最多 log n。它是 Omega(n log n)，因为它是至少 n/2 项的总和，每项至少 log (n/2) = log n - 1。

Answer 3

是的，这是一阶线性递推。是可以准确解决的。如果你的初始值为 $T(1) = 0$，你会得到 $T(n) = \log n!$。您可以近似 $\log n!$ （参见 Stirling 公式）： $$ \lnn！ = n \ln n - n + rac{1}{2} \ln \pí n + O(\ln n) $$

[这里需要 LaTeX！！]

Answer 4

After log(n!) We all know;
    n!=n(n-1)(n-2)....
    n!=n.n.n.n.... 
(because if we consider only highest term then it's n so...)
    n!=n^n

Now put it to our question so,
    T(n)=1+log(n!)
    T(n)=1+log(n^n)
    T(n)=1+n(log(n))   
(According log property)