查找功能的顺序

以下功能的最低顺序是什么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

查找功能的顺序

回答

相关问题