8

挿入ソートの最悪の場合の分析を理解しようとしていますが、スライド21(ppt)に含まれる計算に問題があります。

私は最初の式を理解しています:

Σ(j = 1からn)j = n(n + 1)/ 2

しかし、私が苦労しているこれらは:

  1. なぜ- 1最後にあるのですか?
    Σ(j = 2からn)j = n(n + 1)/ 2-1
  2. また、私はこれを理解していません:
    Σ(j = 2からn)(j-1)= n(n-1)/ 2
4

2 に答える 2

10

1からnまでの数を合計するのはガウスのトリックです。

ガウスのトリック

最初の式

ただし、計算する合計は2、ではなく1で始まります。そのため、式から最初の項(つまり、1)を減算する必要があります。

ここに画像の説明を入力してください

2番目の式

基本的に、1から(n-1)までの合計を計算します。nガウスのトリックをで置き換えるとn-1、彼らが使用する2番目の式を受け取ります。

これは、インデックス変換でも確認できます。

ここに画像の説明を入力してください

ご覧のとおり、合計の境界を調整しました。合計の上限と下限の両方が1減少しました。事実上、これにより合計のすべての項が1減少します。これを修正するには、1を追加する必要があります。 Σの下の項に:(j-1) + 1= j

于 2012-09-21T11:56:23.160 に答える
2

Σ(j=2 to n) j=n(n+1)/2-11ではなく2から始まります。したがって、1を除いて同じ用語が加算されます。したがって、合計は1少なくなります。

Σ(j=2 to n)(j-1)と同じ用語を足し合わせたものΣ(j=1 to n-1)(j)です。したがって、その合計を見つけるには、式でにn置き換えます。n-1n(n+1)/2

于 2012-09-21T11:53:08.257 に答える