algorithm - 对于任意输入n，如何计算插入排序的理论运行时间？

Question

请注意，我在这里以插入排序为例。我在 C.S. 类(class)中分配了一项作业，其中涉及将各种排序算法的结果运行时间与应该发生的理论运行时间进行比较。

例如，假设我有一个由 1000 个随机排序的整数组成的输入数组，并且我在最坏情况的假设下进行操作。结果可能在 320.x 毫秒 左右。然而，理论上，它应该是平坦的 300 毫秒。同样，如果我将输入大小增加到 6000，我可以获得 11,735.577106 毫秒(如我的 C.S. 老师提供的示例所示)；然而，理论上的运行时间将为 10,800 毫秒。

我们知道插入排序的最坏情况性能是f(n) = O(n^2)。不知道 f 的原始定义，我查了一下，发现结果是，

f(n) = ( n(n - 1) + n )/2 = n^2/2。

这引出了算法的递归关系:

T(n) = T(n-1) + f(n)

所以，我决定编写一个小 C 程序并测试输入 1000 的 T(n)，期望得到大约 300000 左右。

#include <stdio.h>

// Recurrence relation for insertion sort ( worst-case )
float T( float n )
{
    if ( n == 1.0f )
        return 1.0f;

    return T( n - 1 ) + n * n * 0.5f;
}

int main( void )
{
    printf( "T( %f ) = %f \n", 1000.0f, T( 1000.0f ) );

    return 0;
}

输出:

T( 1000.000000 ) = 166916608.000000

显然，事实并非如此。

所以，我很难过。

tl;dr

我想知道我的教授如何使用包含 1000 个元素的数组的插入排序达到 300 毫秒的理论运行时间。我的理解是递归关系用于解决这个问题，但显示的代码输出(应该是插入排序最坏情况下的递归关系)没有提供任何清晰的方法来轻松理解这实际上是如何计算的.

Answer 1

如果您想测试最坏的情况，请创建一个按降序排序的数组，然后使用插入排序进行升序排序。

最好的情况是，如果您采用升序排序的数组并尝试通过插入排序来运行它。

获取它们的基准并尝试将它们关联起来。

此外，O(n^2) 并不完全等于 n^2 操作。在大 O 表示法中，O(2(n^2)) 和 O((n^2)/2) 都将表示为 O(n^2)