插入排序分析和求和表示法

Question

我试图理解插入排序的最坏情况分析,我在幻灯片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.