algorithm - 选择排序和求和符号分析

Question

我正在阅读有关选择排序算法分析的本教程(personal.denison.edu/~kretchmar/272/SelectionSortAnalysis.pdf)。我花了相当长的时间来理解算法分析，但并没有完全成功。

如果您查看 PDF，则有一些与 c3、c4 和 c5 相关的“时间”。我不知道作者为什么添加求和符号，为什么选择顶部和底部索引以及为什么在第一次求和后选择“（i + 1）”。我知道求和符号是表达一组数字之和的一种紧凑方式......但我似乎无法完成这个难题。

谢谢

Answer 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次成功，一次不成功，终止循环。因此，在循环体中求和的值为 i，但循环终止测试本身（即 for 语句）的求和值为 i + 1。