计算递归关系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.