插入排序分析和求和符号 [英] Insertion sort analysis and summation notation

问题描述

我想了解插入排序的最坏情况分析，我有一个涉及上的下滑21（PPT）。

据我所知，第一个公式：

但这些我挣扎着：

1. 为什么会出现 - ？1 在最后
   
2. 另外，我不明白这一个：
   

解决方案

这是高斯伎俩从1总结的数字到n：

第一个公式

不过，总和要计算开始在 2 ，不是 1 ，这就是为什么你必须减去第一项（即1）从下式：

第二个公式

实际上，您计算从1之和，直到第（n-1）。如果替换 N 高斯招用 N-1 ，您会收到他们所使用的第二个公式。

您也可以看到这一点的指数转换：

正如你所看到的，我已经调整的总和的界限：无论是上，下之界已经下降了1实际上，这deceases的所有的术语在总和1 ，要纠正这一点，你必须添加1到任期Σ下：（J-1）+ 1 = Ĵ。

I am trying to understand the worst case analysis of Insertion sort and I have a problem with the math involved on slide 21 (ppt).

I understand the first formula:

But these I'm struggling with:

1. Why is there a - 1 at the end?
   
2. Also, I don't understand this one:
   

解决方案

It's Gauss' trick to sum numbers from 1 to n:

First formula

However, the sum you want to compute starts at 2, not 1, that is why you have to subtract the first term (i.e. 1) from the formula:

Second formula

Essentially, you compute the sum from 1 until (n-1). If you substitute n in Gauss' trick with n-1, you receive the second formula they use.

You can also see this with an index transformation:

As you can see, I have adjusted the boundaries of the sum: Both the upper and lower bounds of the sum have been decreased by 1. Effectively, this deceases all terms in the sum by 1, to correct this, you have to add 1 to the term under the Σ: (j-1) + 1 = j.

这篇关于插入排序分析和求和符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！