ログの合計の大きな$ O $ OR $表象は何ですか？

Question

： $$ \ sum ^ {n + m} _ {i= n} \ log（i）$$ 私は大きなo表記が何であるかと思いますか？ 私たちはこのASを書くことができると信じています $$ \ log（n）+ \ log（n + 1）+ \ log（n + 2）+ \ ldots + \ log（n + m）$$

$$ \ log（n + m）！/ \ log（n-1）！$$

ありがとう

Answer 1

$ \ log $ の合計が $ \ log $ と同じです。製品の

それは：

$$ \ log（xy）=log x + \ log y $$

あなたの機能を変更することができます：

$$ \ begin {align} \ sum_ {i= n} ^ {n + m} \ log i＆\ log \ prod_ {i= n} ^ {n + m} i \\ ＆=log（N \ CDOT（N + 1）\ CDOT（N + 2）\ CDOT \ LDOTS \ CDOT（M-1）\ CDot M）\\ ＆=log（m！/ \（n-1）！）\\ \ end {align} $$

その後、これらのバックアウトを取得するには、除算ルールを同様に使用できます。

$$ \ log（m！\ / \（n-1）！）=log（m！） - \ log（（n-1）！） $$

スターリングの近似すぐに見ることができます：

$$ \ log（m！） - \ log（（n-1）！）= O（m \ log m） $$

あなたはより正確な境界を得ることによってより良いことができるかもしれません：

$$ \ begin {align} \ log（m！） - \ log（（n-1）！）＆\ leq em ^ {m + \ frac {1} {2}} e ^ { - m} - \ sqrt {2 \ pi}（n -1）^ {n- \ frac {1} {2}} e ^ {1-n} \\ ＆=vdots. \ end {align} $$

Answer 2

o（（m + 1）log（n + m））。それは明らかに上限です。しかし、ほとんどの値には最大に近い対数がありますので、それはまた良い下限です。

あなたの特にシンプルなケースでは、スターリング式はあなたにもっと良い結果を与えるでしょうが、あなたはビッグOのみを求められます。