问题描述
我们将通过重复替换来解决递归关系:
We are to solve the recurrence relation through repeating substitution:
T(n)=T(n-1)+logn
我开始替换并得到以下内容.
I started the substitution and got the following.
T(n)=T(n-2)+log(n)+log(n-1)
根据对数乘积规则，log(mn)= logm + logn
By logarithm product rule, 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，然后将其代入
We know that the base case is T(1), so n-1=k -> k=n+1, and substituting this in we get
T(n)=T(1)+log[n*(n-1)*...*1]
显然n *(n-1)* ... * 1 = n！所以，
Clearly n*(n-1)*...*1 = n! so,
T(n)=T(1)+log(n!)
我不知道该如何解决.答案是否只是 O(log(n！))?我还读过其他解释，说它是Θ(nlogn)，因此得出O(nlogn)和Ω(nlogn)分别是上限和下限.
I do not know how to solve beyond this point. Is the answer simply O(log(n!))? I have read other explanations saying that it is Θ(nlogn) and thus it follows that O(nlogn) and Ω(nlogn) are the upper and lower bounds respectively.
推荐答案
这会扩展到日志(n！).您可以看到这是因为
This expands out to log (n!). You can see this because
= T(n-2)+ log(n-1)+ log n
= T(n - 2) + log (n - 1) + log n
= T(n-3)+ log(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 1 + log 2 + ... + log (n - 1) + log n
= T(0)+ log n！
= T(0) + log n!
确切的答案取决于T(0)是什么，但是对于任何固定的T(0)恒定值，它都是Θ(log n！).
The exact answer depends on what T(0) is, but this is Θ(log n!) for any fixed constant value of T(0).
注释-使用斯特林逼近，Θ(log n！)=Θ( n登录n).这可能有助于您将其与现有的复杂性类相关联.
A note - using Stirling's approximation, Θ(log n!) = Θ(n log n). That might help you relate this back to existing complexity classes.
希望这会有所帮助！
这篇关于计算递归关系T(n)= T(n-1)+ logn的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！