挿入ソートの最悪の場合の分析を理解しようとしていますが、スライド21(ppt)に含まれる計算に問題があります。
私は最初の式を理解しています:
しかし、私が苦労しているこれらは:
- なぜ
- 1
最後にあるのですか?
- また、私はこれを理解していません:
挿入ソートの最悪の場合の分析を理解しようとしていますが、スライド21(ppt)に含まれる計算に問題があります。
私は最初の式を理解しています:
しかし、私が苦労しているこれらは:
- 1
最後にあるのですか?1からnまでの数を合計するのはガウスのトリックです。
ただし、計算する合計は2
、ではなく1
で始まります。そのため、式から最初の項(つまり、1)を減算する必要があります。
基本的に、1から(n-1)までの合計を計算します。n
ガウスのトリックをで置き換えるとn-1
、彼らが使用する2番目の式を受け取ります。
これは、インデックス変換でも確認できます。
ご覧のとおり、合計の境界を調整しました。合計の上限と下限の両方が1減少しました。事実上、これにより合計のすべての項が1減少します。これを修正するには、1を追加する必要があります。 Σの下の項に:(j-1) + 1
= j
。
Σ(j=2 to n) j=n(n+1)/2-1
1ではなく2から始まります。したがって、1を除いて同じ用語が加算されます。したがって、合計は1少なくなります。
Σ(j=2 to n)(j-1)
と同じ用語を足し合わせたものΣ(j=1 to n-1)(j)
です。したがって、その合計を見つけるには、式でにn
置き換えます。n-1
n(n+1)/2