algorithm - 挿入ソート分析と総和表記

Question

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

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

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

1. なぜ- 1最後にあるのですか？
   
2. また、私はこれを理解していません：
   

Answer 1

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

最初の式

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

2番目の式

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

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

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

Answer 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