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

Question

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

我理解第一个公式:

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

1. 为什么最后有一个- 1？
   
2. 还有，我不明白这个:
   

Answer 1

对 1 到 n 的数求和是高斯的把戏:

第一个公式

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

第二个公式

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

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

如您所见，我调整了总和的边界:总和的上限和下限都减少了 1。实际上，总和中的所有项都减少了 1 ，要更正此问题，您必须在 Σ 下的项中加 1:(j-1) + 1 = j。