1

最も内側のステートメントが実行された合計回数を計算しようとしています。

count = 0;
for i = 1 to n
    for j = 1 to n - i
       count = count + 1

ループが実行できるのはO（n * ni）= O（n ^ 2）であることがわかりました。二重和を使ってこれを証明したかったのですが、j = 1が投入されて方程式を始めるのに苦労しているので、迷子になっています。

誰かが私にこれを説明するのを手伝ってもらえますか？

ありがとう

4

1 に答える 1

2

それぞれについてi、内側のループは時間を実行しn - iます（n一定です）。したがって（からのi範囲である1ためn）、最も内側のステートメントが実行される合計回数を決定するには、合計を評価する必要があります

（n-1）+（n-2）+（n-3）+ ... +（n-n）

用語を再配置する（n最初に表示されるすべてのをグループ化する）ことにより、これが次のように等しいことがわかります。

n * n-（1 + 2 + 3 + ... + n）= n * n-n（n + 1）/ 2 = n *（n-1）/ 2 = n * n / 2-n / 2

これを確認するためのPythonでの簡単な実装は次のとおりです。

def f(n):
    count = 0;
    for i in range(1, n + 1):
        for _ in range(1, n - i + 1):
            count = count + 1
    return count

for n in range(1,11):
    print n, '\t', f(n), '\t', n*n/2 - n/2

出力：

1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
7 21 21
8 28 28
9 36 36
10 45 45

最初の列は、、n2番目は内部ステートメントが実行された回数、3番目は。ですn*n/2 - n/2。

于 2012-11-20T01:03:51.670 に答える