选择排序之和

Question

我正在研究算法设计手册，并在第二章中继续理解选择排序后面的求和。

1. 有人能解释一下这个求和是如何简化的吗？例如，我们如何到达n-i- 1？
2. 如果n= 8，那么s(n)是(8-1)+(8-2)+(8-3)等等。我包括了一张滑翔伞的截图和我的笔记。选择排序的截图

Answer 1

\sum_{i=0}^{j-1} \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^{j-1} n - i - 1，为什么，j在哪里？

您问的是简化的步骤，用它对索引j进行求和。这个链接更详细，但总的来说，

\sum_{j=u}^{v} 1 = -u + v + 1

相当于这个伪码，

sum = 0
for(int j = u; j <= v; j++)
    sum += (f(j) = 1)
return sum

例如，对于u=3和v=22，它将是sum = u - v + 1 = 22 - 3 + 1 = 20。

​

​

使用-u + v + 1 at u = i+1和v = n-1，它简化为-(i+1) + (n-1) + 1 = n - i - 1。

如果n=8 \sum_{i=0}^{n-1} n - i - 1指的是(8-1) + (8-2) + (8-3) + ... + 2 + 1 [+ 0]，为什么是两种不同的值？

它已经从(8-0-1) + (8-1-1) + (8-2-1) + ... (8-5-1) + (8-6-1) + (8-7-1)简化了。