与えられた関数がO（n）であるかどうかを調べるには？

Question

私は私のテストで次の質問を受けました：

次のどれがO（n）にありますか？

a) n + lgn b) n + 2n c) n + n^2 d) 1000n + 4500lgn + 54n

IはO（N）の時間計算量を知っている要素の数は、それが動作増加を完了するのにかかる時間を増加させるように、要素の数に依存します。この論理によれば、aとcはO（n）の時間複雑さを取ると言うのは正しいですか？

Answer 1

は、いくつかの関数f（n）のための2つの正の定数、cとk、例えばc > 0、k > 0、n >= k、及び0 <= f(n) <= cnそれが存在しなければならないということであるO（N）の定義を考えます。 cとkという定数が存在することがわかると、その関数はO（n）です（これらの定数が存在しない場合、関数は実際にはO（n）よりも大きくなります）。

F(n) = n + lg(n)をご覧ください。これはO（n）ですか？もしそうなら、cとkの値を見つけるのに何の問題もないはずです。

0 <= f(n) <= cn 
0 <= n + lg(n) <= cn 

2からkを設定し、nが2（N> = kのため）である基本ケースを考えることができます。

0 <= 2 + lg(2) <= c * 2 
0 <= 2 + 1 <= 2c 
0 <= 3 <= 2c 
0 <= 3/2 <= c 

nが増えるにつれて関数がどのように挙動するかを見てみましょう（n = 4を設定して何が起こるかを見てください）。

0 <= 4 + lg(4) <= c * 4 
0 <= 4 + 2 <= 4c 
0 <= 6 <= 4c 
0 <= 6/4 <= c 
0 <= 3/2 <= c .. take a look at that, it doesn't matter how large n becomes, c is 3/2 

だから私たちは私たちの定数を発見した（C = 3/2、K = 2）ので、この機能は、形式的な定義によるO（n）があります。

F(n) = n + n^2をご覧ください。これはO（n）ですか？実際にはO（n^2）ですが、とにかく値cとkを見つけることができるかどうかを確認できます。

0 <= f(n) <= cn 
0 <= n + n^2 <= cn 

さらに、kを2に設定し、n = kの基本ケースを考慮してください。

0 <= 2 + 2^2 <= c*2 
0 <= 2 + 4 <= 2c 
0 <= 6 <= 2c 
0 <= 3 <= c .. so IF this is O(n), c is at least 3 

（現在はN = 4）

0 <= 4 + 4^2 <= 4c 
0 <= 4 + 16 <= 4c 
0 <= 20 <= 4c 
0 <= 20/4 <= c 
0 <= 5 <= c  .. last time c was 3, now its 5 ... as n increases, c is not constant! 

この関数はO（N）ではない、Nが増加すると何が起こるかを見ることができます - 彼らは単にドンので、我々は、一定の値cとkを見つけることができません存在しない。

f（n）= 5nとします。これはO（n）です（この場合、cは5です）。 f（n）= n * nと考える。これはO（n）ではない（cは定数ではないnに等しい）。私たちが実際に言っているのは、私たちの関数f（n）はある定数で乗算された別の関数g（n）によって束縛されているということです。関数がO（n）であるかどうかを尋ねるとき、g(n) = nとしますが、n^2、lgn、nlgnはすべて興味深い境界です（おそらくテストになります）。

n + n^2 O（n^2）？ c > 0とk > 0、n >= kという値を見つけても問題ありません。つまり、0 <= n + n^2 <= cn^2です。

さらに読むために https://xlinux.nist.gov/dads//HTML/bigOnotation.htmlをご覧ください。