查找函数的顺序

Question

随着n趋于无穷大，下列函数的最低阶数是多少？

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

我的回答：因为ln(1+x) <= x，

因此，f(n) = O(a^n)。我相信这不是一个严格的界限。我也许可以使用来获得更紧密的界限，但我认为它不会改善顺序。任何的想法？请让我知道任何您认为可能有帮助的信息。

Answer 1

答案：O(n^2).

证明：

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*}$

这个估计是最优的，因为所有的不等式实际上都是 asymptotic 等价的。

请注意，这 比您的指数估计小很多。

查找函数的顺序

Find the order of a function

big-o

inequality

logarithm

asymptotic-complexity