algorithm - この選択ソートの実装の大きな複雑さを計算していますか?

Question

この選択並べ替えの実装の時間の複雑さを計算しようとしています。

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

正式には、以下の方法を使用して、成長の順序で正確な反復回数を取得できます。

次のフラグメント コード (元のコードの合成バージョン) を実行sumすると、閉じた形式の T(n) と等しくなります。

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