寻找一个函数的阶数

Question

寻找一个函数的阶数

big-oasymptotic-complexitylogarithminequality

3

当 n 趋向于无穷大时，以下函数的最低阶是什么？

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

我的答案：由于 ln(1+x) <= x，

因此，f(n) = O(a^n)。我确定这不是一个紧密的限制。我也许能够使用

来获得更紧密的限制，但我不认为它会改善顺序。有什么想法吗？请让我知道任何可能有帮助的信息。

- Sus20200

如果a<1，则f(n)<0。也许你的意思是a>1而不是a>0？ - sds

@sds 对，谢谢你让我知道了。 - Sus20200

请把这个问题移动到[Math.SE]或[cstheory.SE]。 - sds

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sds · Accepted Answer

答案：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*}$

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

请注意，这比你的指数估计要小得多。