查找功能的順序

以下功能的最低順序是什麼n趨於無窮？查找功能的順序

其中a>1和0<p<1。

我的回答：由於ln(1+x) <= x，

因此，f(n) = O(a^n)。我相信這不是一個嚴格的限制。我可能可以使用來獲得更緊的界限，但我認爲它不會改善順序。任何想法？請讓我知道任何你認爲可能有用的事情。

來源

2017-07-17 Sus20200

如果a <1，則f（n）<0。也許你的意思是> 1而不是> 0？ – sds

@sds正確。謝謝你讓我知道。 – Sus20200

請將此問題移到[Math.SE]或[cstheory.SE]。 – sds

答案：O(n^2)。

證明：因爲所有的不平等實際上asymptotic等價

f(n) = sum(i,log(pa^i+(1-p))) 
    = sum(i,log(p*a^i(1+(1-p)/(pa^i)))) 
    =< sum(i,i*log(a)) + sum(i,log(p)) + sum(i,(1-p)/(pa^i)) 
    =< n*(n+1)*log(a)/2 + n*log(p) + (1-p)/p * 1/(1-1/a)

$\begin{align*} f(n) &= \sum_{i=0}^{i=n}\log(pa^i+(1-p)) \\ &= \sum_{i=0}^{i=n}\log(pa^i(1+\frac{1-p}{pa^i})) \\ &\le \sum_{i=0}^{i=n}i\log(a) + \sum_{i=0}^{i=n}\log(p) + \sum_{i=0}^{i=n}\frac{1-p}{pa^i} \\ &\le \frac{n(n+1)\log(a)}{2} + n\log(p) + \frac{1-p}{p} \times \frac{1}{1-\frac1a} \end{align*}$

這估計是最優的。

注意，這是比你的指數估計小多。

來源

2017-07-17 23:17:41 sds

太棒了！你是怎樣找到它的？ – Sus20200

@ Sus20200：wdym？ – sds

我的意思是我很驚訝。 – Sus20200

查找功能的順序

回答

相關問題