forループを調べてBig Oのパフォーマンスを調べるにはどうすればよいですか？

Question

私はBig O Notationについて学び始めました。正直なところ私はそれを抱いているとは思っていません。ループを探すだけでO（）パフォーマンスをどのように決定するのかよくわかりません。私はいくつかの例を挙げておき、正しいと思う答えをいくつか挙げました！彼らが間違っていて、どんな説明も大いに評価されるなら、私に知らせてください！

for (int i = 0; i <1000; i++) { 
     count ++; 

これはO（n）と思われます。これは、定刻印刷以外のforループでは何も起こっていないからです。私たちは 'n'回、この場合は1000回繰り返すのですか？

for (int i = 0; i < n; i++) { 
    for(int j = 0; j < n; j++) 
     count ++; 

ループをn入れ子にし、それが二回反復し、N、N *されているので、この1つは（N^2）Oを持っていますか？

for (int i = 0; i < n; i++) { 
    for(int j = i; j < n; j++) 
     count++; 

最悪の場合はO（n^2）ですか？または、これはO（n log n）ですか？

Answer 1

Big-O表記は、入力時にランタイムがどのように増加するかを理解するのに役立つガイドです。

最初の例では、nに関係なく、ループは正確に1000回実行されるため、O(1000) = O(1)時間です。

第2の例では、ネストされたループは、外側ループが実行されるたびにn回実行されるたびにn回実行されます。これは合計でn*n = n^2の操作です。したがって、操作の数はnの2乗に比例して増加するため、O(n^2)と言います。

3番目の例では、まだO(n^2)です。 Big-O表記は、時間の複雑さの正確な公式で定数を無視するためです。 jの実行回数がiと計算されると、このパターンが得られます。

i: 0 1 2 3 ... 
j: n n-1 n-2 n-3 ... 

合計で、操作回数は約1/2 n^2です。 Big-O表記は定数を無視するので、これはまだですO(n^2)