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。