当 n 趋向于无穷大时,以下函数的最低阶是什么? 其中 a>1 且 0<p<1。 我的答案:由于 ln(1+x) <= x, 因此,f(n) = O(a^n)。我确定这不是一个紧密的限制。我也许能够使用来获得更紧密的限制,但我不认为它会改善顺序。有什么想法吗?请让我知道任何可能有帮助的信息。
答案: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) 这个估计是最优的,因为所有不等式实际上都是渐近等价的。请注意,这比你的指数估计要小得多。