アルゴリズムの最悪の場合の時間の複雑さ

StackOverflow https://stackoverflow.com/questions/331295

質問

最悪の場合の時間の複雑さt（n）とは：- 私はアルゴリズムについて、そして例としてこの本を読んでいます 選択ソートアルゴリズムのように...のT（n）を取得する方法

selectionSort（A [0..n-1]）を扱っている場合のように

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

擬似コードを書かせてください

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

-------- C＃でも記述します------------------- 

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

t（n）の取得方法、または既知の最悪の場合の時間の複雑さの取得方法

役に立ちましたか？

解決

@ サラジョン 参照したスライドセットとその中のアルゴリズム

forループの各プリミティブ/アトミック操作の複雑さを測定しています

for(j=0 ; j<n ; j++)
{
    //...    
}

スライドでは、次の理由でこのループを2n + 2と評価しています。

  • j = 0（+1 op）の初期セット
  • jの比較<！> lt; n（n ops）
  • j ++の増分（n ops）
  • j <！> lt;かどうかを確認する最終条件。 n（+1 op）

    • 次に、forループ内の比較

    if(STudID == A[j])      
    return true;

    これは、n opsと評価されます。したがって、+ 1 op、n ops、n ops、+ 1 op、n ops = 3n + 2の複雑度を合計した場合の結果です。 T（n）= 3n + 2

    T（n）はO（n）と同じではないことを認識してください。

    他のヒント

    それはO（n ^ 2）です。

    理由は、単一のforループが別のforループにネストされているためです。内側のforループの実行時間O（n）は、外側のforループの繰り返しごとに発生します。これもやはりO（n）です。これらがそれぞれ個別にO（n）である理由は、入力のサイズを指定すると線形の時間がかかるためです。入力が大きいほど、線形スケールnにかかる時間が長くなります。

    この場合は簡単な数学を計算するには、内側のループの複雑さと外側のループの複雑さを掛け合わせます。 n * n = n ^ 2。なぜなら、外側のループのnごとに、内側のnを再度実行する必要があるからです。明確にするために：各nに対してn回。

    O（n * n）。

    O（n ^ 2）

    ところで、複雑さ（big-Oで示される）とT関数を混同しないでください。 T関数は、特定の入力に対してアルゴリズムが通過する必要があるステップの数です。

    したがって、T（n）の値は実際のステップ数ですが、O（何か）は複雑さを示します。従来の表記法の乱用では、T（n）= O（f（n））は、関数T（n）が他の関数f（n）とほとんど同じ複雑さであることを意味します。その複雑さのクラス。

    これは、全体像に焦点を当てることができるため便利です。長い間で、どのように実行するかを見ることで、非常に異なる外観のT（n）関数を持つ2つのアルゴリズムを簡単に比較できます。 run <！> quot;。

    別の博士課程コンプのフラッシュバックはこちら。

    最初に、T関数は、アルゴリズムがタスクを実行するために要する単純な時間の長さです（通常は、いくつかのステップについて）。何と<！> quot; step <！> quot;は、用途によってある程度定義されています。たとえば、ソートアルゴリズムでは比較の数を数えるのが一般的ですが、検索アルゴリズムでは検索される要素の数です。

    アルゴリズムの最悪の場合について話すとき、通常は<！> quot; big-O表記<！> quot;で表します。したがって、たとえば、バブルソートにはO（n <！>＃178;）時間かかると聞きます。大きなO表記を使用する場合、実際に言っているのは、ある関数（この場合はT）の成長は、他の関数の成長に定数を掛けたものよりも速くないということです。それは

    T（n）= O（n <！>＃178;）

    は任意の n を意味し、どんなに大きくても、定数 k があり、その T（n）<！>＃8804; kn <！>＃178; 。ここでの混乱のポイントは、<！> quot; = <！> quot;を使用していることです。オーバーロードされた方法で署名します。つまり、数値的には2つが等しいというわけではなく、 T（n）は kn <！>＃178; 。

    拡張質問の例では、forループとテストの比較数をカウントしているようです。コンテキストと彼らが答えている質問を見ることができると助かります。ただし、いずれにせよ、big-O表記が好きな理由を示しています。 W（n）は O（n）です。 （証明：定数k、すなわち5が存在し、その W（n） <！>＃8804; k（3n）+2に続いて、 O（n ）。）

    これについて詳しく知りたい場合は、アルゴリズムの紹介、コーメンその他

    疑似テーブルを作成して、ハッシュテーブルから学生情報を検索、挿入、削除します。最良および最悪のケースの時間計算量を計算します

    ループに関する限り、

    3n + 2が正解です。ループの各ステップで、3つのアトミック操作が実行されます。 j ++は実際には1つではなく2つの操作です。とj     

    ライセンス： CC-BY-SA と 帰属
    所属していません StackOverflow
    scroll top