3

最悪の場合の時間複雑性 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）を取得する方法、または既知の最悪の場合の時間の複雑さ

4

6 に答える 6

13

それは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)

于 2008-12-01T16:22:10.320 に答える
3

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

したがって、T(n) の値は実際のステップ数であり、O(何か) は複雑さを表します。従来の表記法の乱用により、T(n) = O( f(n) ) は、関数 T(n) が別の関数 f(n) と同じ複雑さしかないことを意味します。これは通常、可能な限り単純な関数です。その複雑さのクラスの。

これは、全体像に集中できるため便利です。「長期的に」どのように機能するかを調べることで、非常に異なる T(n) 関数を持つ可能性のある 2 つのアルゴリズムを簡単に比較できるようになりました。

于 2008-12-01T17:11:43.170 に答える
1

ここに別の博士号のフラッシュバック。

まず、T関数は、アルゴリズムがタスクを実行するのにかかる時間（通常はいくつかのステップで、これについては以下で詳しく説明します）です。「ステップ」とは、使用によってある程度定義されます。たとえば、並べ替えアルゴリズムでは比較の数を数えるのが一般的ですが、検索アルゴリズムで検索される要素の数です。

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

T（n）= O（n²）

は、任意のnに対して、どんなに大きくても、T（n）≤kn²である定数kが存在することを意味します。ここでの混乱のポイントは、オーバーロードされた方法で「=」記号を使用していることです。これは、数値的な意味で2つが等しいという意味ではなく、 T（n）がkn²によって制限されていると言っているだけです。 。

拡張された質問の例では、forループとテストでの比較の数をカウントしているように見えます。彼らが答えている文脈と質問を見ることができるのは助けになるでしょう。ただし、いずれの場合も、big-O表記が好きな理由を示しています。ここでのW（n）はO（n）です。（証明：定数k、つまり5が存在し、そのW（n） ≤k（3n）+2。これはO（n）の定義に従います。）

これについて詳しく知りたい場合は、Cormenetal。によるIntroductiontoAlgorithmsなどの優れたアルゴリズムのテキストを参照してください。

于 2008-12-01T18:31:15.723 に答える
1

@ sara jons 参照したスライド セットとその中のアルゴリズム

forループ内のプリミティブ/アトミック操作ごとに複雑さが測定されています

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

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

  • j=0 の初期セット (+1 op)
  • j < n (n ops) の比較
  • j++ のインクリメント (n ops)
  • j < n (+1 op) かどうかを確認する最終条件

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

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

    これは、n ops と評価されます。したがって、+1 操作、n 操作、n 操作、+1 操作、n 操作を合計すると、結果は 3n+2 複雑になります。したがって、T(n) = 3n+2

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

    于 2008-12-01T17:02:02.800 に答える
    0

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

    于 2010-09-12T18:21:31.930 に答える
    0

    ハッシュテーブルから学生情報を検索、挿入、および削除するための擬似コードを記述します。最良の場合と最悪の場合の時間計算量を計算する

    于 2009-10-02T08:36:50.240 に答える