algorithm - 计算这个选择排序实现的大 O 复杂度？

Question

我正在尝试计算此选择排序实现的大 O 时间复杂度：

void selectionsort(int a[], int n)                    
{
    int i, j, minimum, index;                       
    for(i=0; i<(n-1); i++)                       
    {
        minimum=a[n-1];                      
        index=(n-1);                             
        for(j=i; j<(n-1); j++)                   
        {
            if(a[j]<minimum)                     
            {
                minimum=a[j];                               
                index=j;
            }
        }
        if (i != index)
        {
            a[index]=a[i];
            a[i]=minimum;
        }
    }
}    

我该怎么做呢？

Answer 1

让我们先看看外循环的内部。它对初始分配执行 O(1) 工作，然后有一个运行 n - i 次的循环，然后在最后执行 O(1) 更多工作以执行交换。因此，运行时间为 Θ(n - i)。

如果我们从 i 从 0 到 n - 1 求和，我们得到以下结果：

n + (n - 1) + (n - 2) + ... + 1

这个著名的总和为 Θ(n ² )，因此运行时间为 Θ(n ^{2 )，与}该算法的已知运行时间相匹配。

希望这可以帮助！

Answer 2

形式上，您可以使用以下方法获得具有增长顺序的确切迭代次数：

执行以下片段代码（原始代码的合成版本），sum将等于 T(n) 的封闭形式。

sum = 0;
for( i = 0 ;  i < ( n - 1 ) ; i ++ ) {    
    for( j = i ; j < ( n - 1 ) ; j ++ ) {
        sum ++;
    }
}