このコードの上限であるBig Oとは

Question

私はちょっと混乱しています。私は数時間前にBig O時間の複雑さを研究し、ここですべての記事を読んでいます。

int myfunc(int n) 
{ int result = 0; 
    for (int i = 0; i<n; i++) 
    for (int j = i; j>0; j--) 
     if (i%j == 0) 
     result += j; 
    return result; 
} 

私はこのコードを私に提示しました。私はこのコードの上限を見つけたいと思います。

ここまで私が学んだことから、これは入れ子にされたループなので、上限はO（n^2）と仮定します。しかし、JはIとリンクしているため、私はこのコードが実際にO（n log n）であるかどうか疑問に思っています。私はO（n log n）の概念を完全に理解していないと言います。しかし、私はO（1）、O（n）、O（log n）、O（n^2）、O（n！）などの他のすべての表記を理解しています。

Answer 1

外側ループの繰り返しごとに、内側ループは正確にi回です。

i = 0のとき、内部ループは0回実行されます。

i = 1のとき、内部ループは1回実行されます。

i = 2のとき、内部ループは2回実行されます。

...

場合、I = N-1、内部ループの実行のn-1回。 （n-1））/ 2 =（n-2） - （n-1）= 0 + 1 + 2 + ... +（n-1） n）/ 2となる。したがって

、=（N^2 - n）の関係の計算の総数だから/ 2

を、与えられたコード= O（N^2）の時間複雑。

Answer 2

答えはO（n^2）です。

i変数を行列の行番号とし、jを列番号とします。このループを使用すると、行列の半分だけが見えます。これはO（0.5n^2）の時間複雑さを与えますが、これはちょうどO（n^2）です。

Oの例（）N（ログ）複雑アルゴリズムは数字のソートされたリスト上のバイナリ検索です：あなたはO（n）をn個（ログ）を理解する手助けしようとする

。各比較時に設定された問題の半分は、中央の要素をチェックし、見ている番号の上か下のリストの半分を破棄します。

長さnのn個の異なるセットに対して同じバイナリ検索を行うと、時間の複雑さO（n log（n））が発生します。

Answer 3

内側ループが開始され、外側ループによって制御されるによってi回、iが増加します。

したがって、内側ループは、外側ループによって1、2、3、...、nを受信し、1 + 2 + 3 + ... + n = n(n+1)/2

n(n+1)/2 = (n^2)/2 + n/2を繰り返す内部ループまで沸騰する、反復します。この関数の成長はn^2によって支配されているため、上限はO(n^2)と言えるでしょう。

実行したばかりのシミュレーションを確認してください。