recursion - 计算递归关系 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!)。
注释 - 使用 Stirling's approximation , Θ(log n!) = Θ(n log n)。这可能会帮助您将其与现有的复杂性类联系起来。
希望这可以帮助!