選択並べ替えアルゴリズムの分析に関するこのチュートリアルを行っていました(personal.denison.edu/~kretchmar/272/SelectionSortAnalysis.pdf)。私はアルゴリズム分析の理解にかなりの時間を費やしてきましたが、完全に成功したわけではありません。
PDF を見ると、c3、c4、c5 に関連付けられた特定の「時間」があります。なぜ著者が総和記号を追加したのか、なぜ彼がトップとボトムのインデックスを選んだのか、なぜ最初の総和の後に '(i+1)' を選んだのか、私にはわかりません。総和表記が一連の数値の総和をコンパクトに表現する方法であることは理解していますが、パズルを完成させることができないようです。
ありがとう
1) 彼は外側のループ (1 行目) からの値を合計しています。そのため、彼は i (外側のループからのインデックス変数) を使用します。
2) 開始値が終了値より小さい Σ 式を記述するのは伝統的です。ただし、この場合、一部の i に対して内側のループが実行される回数は n - i です。i が 1 (ループの開始) の場合、内側のループは n - 1 回実行され、外側のループの最後で i が n - 1 になると、内側のループは 1 回実行されます (n - ( n - 1))。したがって、これを sum(i = n-1 -> 1) と書きたいと思うかもしれませんが、先ほど言ったように、最小から最大の順に書くのが伝統です。
3) ループは i 回実行されますが、ループ テストは i + 1 回実行されます。つまり、i 回成功し、1 回失敗して、ループが終了します。したがって、ループ本体内で合計された値は i ですが、ループ終了テスト自体 (つまり、for ステートメント) で合計された値は i + 1 です。