2

重複の可能性：
Big O：依存関係のあるネストされたForループ

次のネストされたループを考えると、BigOの複雑さを理解する必要があります。

for(i=0 to n)
    for(j=n-1;j>=i;j--)

これが複雑になることはわかっていますがO(n^2)、内部ループの式を理解する方法がわかりません。

わかりやすくするために、表を書きました。

n=10
i | j | outer iters | inner iters
0 | 9 |     1       |     10
1 | 9 |     2       |      9 
...
9 | 9 |    10       |      1

したがって、外側のループは実行され、内側のループはn実行されsum(n to n-9)ます。

私は答えがであると言われましたn(n-2)/2、そして私は単に私が持っているものからこの結論に到達する方法を理解することができません。

支援をいただければ幸いです。

4

3 に答える 3

4

外側のループの反復ごとに内側のループが実行される回数を観察します。

When i=0, the inner loop has n iterations.
When i=1, the inner loop has n-1 iterations.
When i=2, the inner loop has n-2 iterations.
......
When i=k, the inner loop has n-k iterations.
.....
When i=n-2, the inner loop has 2 iterations.
When i=n-1, the inner loop has 1 iterations.

したがって、内側のループの反復回数の合計は 1 + 2 + ... + (n-2) + (n-1) + n であり、これは n(n+1)/2 に等しくなります。

于 2012-09-24T16:16:42.157 に答える
1

1 から n までの整数の合計は、ガウスのよく知られたトリックです。

ガウスのトリック
( では+ 1ありませんのでご注意ください- 2)

直感の構築

この式が真である理由を直感的に確認する方法を次に示します。

説明

で自分の目で確かめてみてください1 + 2 + 3 + 4 + 5 + 6

私たちの直感を証明する

しかし、項の数が偶数でない場合はどうなるでしょうか。それはまだ動作しますか？任意の数の用語で機能しますか? これに答えるには、
仮説を証明するのが最善です。

仮説
数学的帰納法という概念で。
このためには、まず基本ケースを確立する必要があります。このケースではn = 1、これは自明に正しいです。

さて、誘導ステップのために。nこの知識に基づいて、いくつかの に対する仮説がすでに証明されていると仮定して、それが にも当てはまることを示したいと思いn + 1ます。これが成功すれば、すべての自然数について「魔法のように」証明されたことになります。なんで？で動作することは既に示しましn = 1た。n => n + 1ステップはn = 2、 で証明されたことを意味します。これは、 などでも証明されたことを意味しますn = 3。これはドミノ効果です。

誘導ステップ

仮説に を代入nするとn + 1、帰納的ステップの結果が得られます。したがって、式がすべての に対して正しいことが証明されましたn。

于 2012-09-25T09:10:15.247 に答える
1

1 回目の反復 -- 内側のループ n-1 回 2 回目の反復 -- 内側のループ n-2 回など

for n-1 iteration -- 内部ループ 1 回

反復の総数 = (n-1)+(n-2)+..2+1 =n(n-1)/2

f(n)= n^2-n/2 と g(n)=n^2 のように書くことができるので、もちろん O(n^2) です。

0<=f(n)<=cg(n) for c>0 n0>0 と書くことができます ここで n は n0 より大きい

于 2012-09-24T16:18:39.157 に答える