插入排序最差情况下运行时间

问题描述：

为什么在最坏的情况下运行时插入排序的复杂性是n（n-1）/ 2〜n^2？突出显示2除？插入排序最差情况下运行时间

答

运行时间不n(n-1)/2，每一步都需要更多的则1 机OP（在所有的机器，我所知道的）。这就是为什么我们通常使用使用big O notation和“忽略”算法中的常量分析 - 我们希望使我们的分析通用和平台独立。
插入排序被分析为n(n-1)/2 = O(n^2)，因为它是 sum of arithmetic progression。第一次迭代需要1 步骤，第二步需要n步，所以我们从算术级数的总和中获得1 + 2 + ... + n = n(n-1)/2。

我理解算术级数的一部分，但是我不清楚除2的分数在哪里？ – user1475421

@ user1475421第一次迭代迭代是1步，第二步是2步，3rs是3步，...第n步是n步，给你总共1 + 2 + 3 + ... + n'步，其总和为“n（n-1）/ 2”。你问为什么1 + 2 + ... + n'总和为'n（n-1）/ 2'？ – amit

我明白n（n-1）的部分，但不知道/ 2部分适合在哪里？ – user1475421

答

算法导论给插入排序的第2.1章节的细节，讨论插入排序的全过程。

最坏的情况是由相反顺序的子阵列切换引起的。

所以，我花时间阅读你所建议的章节。我甚至去购买它。绝对物有所值。不要对此作出否定，该章没有说明算术级数为什么被2除？ – user1475421

这只是一个简单的算术进程总和的结果，当高斯解决它作为一个孩子时，它是着名的。 –

我们可以这样推导出这样一个表达式：将第一个和最后一个作为一对，然后将第二个和最后一个作为一对，等等。显然，所有的对的总和相等。将总和定义为s1。所以，为了得到原始和，我们可以重复n次s1并除以2，因为我们再一次重复原始和。 –

答

我知道这已经永远关闭了，但我想补充一点，这个对于那些试图在插入排序最坏的情况下进行数学研究的人来说。我发现了一个伟大video即（N-1）/ 2公式这样解释了N：

评价的总和：

enter image description here

你首先将它拖放到一系列符号（称之为IT方面）：

s = 1 + 2 + 3 + ... n-3+n-2+n-1

然后显示它在反向：

s = n-1+n-2+n-3+ ... 3 + 2 + 1

加s通过增加每对送在一起，你会得到：n+n+n+....n+n+n

或者换句话说2s = n(n-1)因为你有N，N-1次，并把你的套二来得到它。

那么你只需要解决不等式2s = n(n-1)哪些来s = n(n-1)/2。