algorithm - 插入排序分析和求和符号

Question

我试图了解插入排序的最坏情况分析，但我对幻灯片 21 (ppt)中涉及的数学有疑问。

我理解第一个公式：

但我正在努力解决这些问题：

1. 为什么最后有a - 1？
   
2. 另外，我不明白这个：
   

Answer 1

从 1 到 n 的数字相加是高斯的诀窍：

第一个公式

但是，您要计算的总和从 开始2，而不是1，这就是为什么您必须从公式中减去第一项（即 1）：

第二个公式

本质上，您计算从 1 到 (n-1) 的总和。如果你用 替换n高斯的技巧n-1，你会得到他们使用的第二个公式。

您还可以通过索引转换看到这一点：

正如你所看到的，我已经调整了总和的边界：总和的上限和下限都减少了 1。实际上，这会使总和中的所有项都减少 1，要纠正这个问题，你必须加 1到 Σ 下的项：(j-1) + 1= j。

Answer 2

Σ(j=2 to n) j=n(n+1)/2-1从 2 而不是 1 开始。所以除了 1 之外，它是相同的项加在一起。所以总和少了 1。

Σ(j=2 to n)(j-1)是与 相同的项加在一起Σ(j=1 to n-1)(j)。所以要在公式中找到它的总和替换n为。n-1n(n+1)/2