関数の次数を求める

nが無限になる傾向にあるので、次の関数の最下位は何ですか？関数の次数を求める

a>1および0<p<1。

私の答え：

したがって、ln(1+x) <= x以来、f(n) = O(a^n)。私はこれが緊密な境界ではないと確信しています。私はを使用してより厳密な境界を得ることができるかもしれませんが、私はそれが順序を改善するとは思いません。何か案が？私があなたに役立つと思われることを教えてください。

出典

2017-07-17 Sus20200

a <1の場合、f（n）<0です。おそらく> 0ではなく> 1を意味しますか？ – sds

@sds right。知らせてくれてありがとうございます。 – Sus20200

この質問を[Math.SE]または[cstheory.SE]に移動してください。 – sds

回答：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等価であるため、この推定値が最適です。

これはです。指数関数的な見積もりよりも小さいです。

出典

2017-07-17 23:17:41 sds

それは素晴らしいです！どうやって分かったの？ – Sus20200

@ Sus20200：wdym？ – sds

私は驚いています。 – Sus20200

答えて

関連する問題