3

以下は私の挿入ソートコードです：

void InsertionSort(vector<int> & ioList)
{
  int n = ioList.size();
  for (int i = 1 ; i < n ; ++i)
  {
    for (int j = 0 ; j <= i ; ++j)
    {
      //Shift elements if needed(insert at correct loc)
      if (ioList[j] > ioList[i]) 
      {
        int temp = ioList[j];
        ioList[j] = ioList[i];
        ioList[i] = temp;
      }
    }
  }
}

アルゴリズムの平均的な複雑さは O(n^2) です。

ビッグ O 表記についての私の理解から、これは、この場合、2 つのループを実行するためです (外側のループは n-1 回、内側のループは 1,2,...n-1 = n(n-1)/2 回、したがって結果として得られるアルゴリズムの無症候性の複雑さは O(n^2) です。

これで、入力配列が既にソートされている場合が最良のケースであると読みました。そして、そのような場合、アルゴリズムの大きな O の複雑さは O(n) です。しかし、どちらの場合 (平均的な場合と最良の場合) でも、ループを同じ回数実行し、要素を比較する必要があるため、これがどのように可能であるかを理解できません。回避される唯一のことは、要素のシフトです。

複雑さの計算には、このスワッピング操作のコンポーネントも含まれますか?

4

2 に答える 2

8

はい、これは実装が正しくないためです。内側のループは から まで逆方向にカウントi-1し、よりも小さい0要素を見つけるとすぐに終了する必要があります。ioList[j]ioList[i]

最良のケースでアルゴリズムが O(n) 時間で実行されるのは、その終了基準のためです。

入力リストがすでにソートされている場合、内側のループは任意の に対してすぐに終了しますi。つまり、実行される計算ステップの数は、外側のループが実行される回数、つまり O(n) に比例します。

于 2012-11-05T09:34:15.360 に答える
7

「挿入ソート」の実装が不十分です。

i-1内側のループでは、より大きい各要素を交換するまでスキャンしないでくださいioList[i]。i-1代わりに、新しい要素を挿入する正しい場所が見つかるまで (つまり、新しい要素以下の要素が見つかるまで)から逆方向にスキャンし、そこに挿入する必要があります。入力が既にソートされている場合、正しい挿入ポイントは常にすぐに見つかるため、内側のループはi-11 回だけ実行されます。

また、外側のループの反復ごとに常に操作を実行するため、並べ替えは平均して挿入並べ替えよりも悪くなります。i+1これらの操作の一部は単なる比較であり、比較の後にスワップが続くものもあります。ランダム/平均入力の場合、正しい挿入ポイントは最初にソートされたセグメントの途中であるため、挿入ソートは平均でその半分だけを行う必要があります。各操作が比較とコピーになるように、スワップを回避することもできます。

于 2012-11-05T09:35:21.193 に答える