c++ - ネストされた for ループの実行時間

Question

次のアルゴリズムの実行時間

int b = 0;
for (i = 0; i < n; i++) 
    for (j = 0; j < i * n; j++)   
        b = b + 5;

最初のループがO(n)であることは知っていますが、それは私が得た限りです。2 番目のループはO(n^2)かもしれないと思いますが、考えれば考えるほど意味がなくなります。どんなガイダンスでも大歓迎です。

Answer 1

このコードの実行時間を n の関数として表現したいと思います。これを呼び出しますT(n)。

との関数としての内側のループの実行時間はT(n) = U(0,n) + U(1,n) + ... + U(n-1,n)と言えます。U(i,n)in

内側のループは時間を実行i * nします。U(i,n)ちょうどそうですi * n。

それで、それがわかりましたT(n) = 0*n + 1*n + 2*n + ... + (n-1)*n = n * (1 + 2 + ... + (n-1))。

の閉形式(1 + 2 + ... + (n-1))は(n^2 - n)/2 http://www.wolframalpha.com/input/?i=1+%2B+2+%2B+...+%2B+(n-1)です。

だから私たちはそれを得るT(n) = n * (1 + 2 + ... + (n-1)) = n * ((n^2 - n)/2) = (n^3 - n^2) / 2、

ですO(n^3)。

Answer 2

easiest way would be to use a example

assume n=10 

1st for loop runs 10 times o(n)
2nd loop loop runs 0 if i=0
                   10 time for i=1
                   20 times for i=2
                   30 times for i=3
....  100 times(for i=10) o(n^2)

hope it helps you

Answer 3

n反復のために外側のループが実行されます。

nが 0 の場合、内部ループの実行回数0*n=0回nが 1 の場合、内部ループの実行回数1*n=n回nが 2 の場合、内部ループの実行回数2*n=2n回nが 3 の場合、内部ループの実行回数3*n=3n回 ... ...nが n の場合、内部ループの実行回数n*n=n*n回

したがって、内側のループは合計で次を実行するように見えます。

0 + n + 2n + 3n + ... + n*n 

これに外側のループを掛けるnと、約になります。O(n^3)複雑さ。