Big-Oh：O（g（n））= 10^nのf（n）= 3^nですか？

-1

私はこれを証明できますが、なぜ3^nがO（10^n）にあるのかを概念的に理解していません。私が間違っている？Big-Oh：O（g（n））= 10^nのf（n）= 3^nですか？

'3^n'は' 10^n'より漸近的に速く成長しないので、 'O（10^n）'にあります。もちろんそれは厳しいものではありません。 '3^n'も' O（3^n） 'にあります。これはタイトな境界です。 – Paulpro

'h（n）= 1'と' i（n）= n'も 'O（10^n）'にあります。 – Paulpro

概念的には、指数部の基底が大きいほど、関数の成長が速くなります。

Big-Oは上限を与えます。すなわち、f(n)とg(n)の2つの関数を指定した場合、nの値がある一定のしきい値（定数倍のような細かい部分を除いて）の場合、g(n)がf(n)を支配する場合は、f(n) = O(g(n))と言います。

ここで、n >= 0については、3^nよりも少なくとも10^nが大きい（しかしほとんどの時間ははるかに大きい）ことが明らかです。

3^n = O(10^n)と言っても特に意味はありません。これは決して厳しいものではありません。これら2つの機能の成長率は大きく異なります。 3^nのより有効な範囲は、—、すなわち3^n = O(3^n)である。

2016-04-06 01:18:03 Purag

ええ、それはまさに私が考えたものです。それがo（g（n））とみなされた場合、混乱していました！私はちょうどそれが有用でないとしても正しいと確信したかった。 – TimelordViktorious

はい、実際には正しいですが、有用ではありません。 '1 = O（10^n）'と言うこともできます。これは本当ですが、実際には役に立たないのです。順序1関数は定数ランタイムを持ち、順序10^n関数は指数関数的に悪いランタイムを持ちます。 – Purag

@ MH1993 'o'（little-oh）と' O'（big-oh）で書くときは注意が必要です。彼らは2つの異なることを意味します。「o」は縛られていないことを意味します。「O」は意味を持ちます。 'o'は' <= 'と' <'に' 'です。 – Paulpro

答えて