0

アルゴリズムが O(n) 時間または O(nlogn) 時間で実行されるかどうかを知るにはどうすればよいですか?

4

3 に答える 3

2

さて、ここに私の最初の答えがあります...

アルゴリズムの O() 表記 (ただし、任意の関数に適用できます) は、アルゴリズムの成長率の上限のようなものです。おそらく関心があるのは、特定の入力サイズに対してアルゴリズムが実行する操作の数を関連付ける関数です。あなたは段階的なアプローチを求めているようですので、私はそれを試みます：

  1. n の入力サイズ (または n 要素の既存のデータ構造など) に対してアルゴリズムによって実行される操作の最悪のケースの数を記述する関数を記述します。

  2. Big-O 記法の定義を使用してその関数を単純化します。ほとんどの場合、これは非常に簡単です。ただし、場合によっては、数学的形式と big-O の実際の意味を理解する必要があります。教科書やコンピュータ サイエンスの教授が説明する方がよいので、ここでは説明しません。詳細を無視して、項 (項の合計の場合) を最大に成長する関数に保持し、他のすべてを取り除きます。その項に定数係数がある場合は、それらも取り除きます。例: f(n) = 4n^2 + 10000n + 500 は、4n^2 項が他の 2 つの項よりも速く成長し、係数 4 が削除されるため、前述の方法で n^2 になるように変更されます。n^2 のままです。

次に例を示します。Listが数値の配列で、lSizeが配列内の項目の数であるとします。

for (int i=0; i < lSize; ++i){
  for (int j = i+1; j<=lSize; ++j){
    if (List[i] > List[j]){ //swap the elements
      int temp = List[i];
      List[i] = List[j];
      List[j] = temp;
    }
   }
}

上記の選択並べ替えアルゴリズムを使用して、n 個の項目のリストを並べ替えるために必要な操作の数を数えましょう。

ステップ1

リストのサイズが n の場合、このアルゴリズムで並べ替えるには (n に関して) いくつの操作が必要ですか? ここで lSize は n の値を取ります。2 つの for ループがあり、一方が他方の内部にネストされています。外側のループは簡単です。リスト内のすべての要素に対して 1 回実行されます。またはn回。そのループ内には別の for ループがあり、操作の数はすぐにはわかりません。このループの反復回数は、外側の for ループの i の現在の値によって異なります。いくつかのテスト値を使用して座って、出現するシリーズを書き出すと、内側のループが最初に n 回実行され、次に (n-1) 回、次に (n-2) 回実行され、合計カウントが次のように実行されることがわかります。 n + (n-1) + (n-2) ... 2 + 1. これは 1 から n までのすべての数値の合計であることがわかります。n = 100 の場合、内側のループの合計反復回数は 100 + 99 + 98 + 97 ... になります。2 + 1. これは算術級数であり、n 個の項目を次のように簡略化できます: n*(n-1)/2。これは、内側のループ内の操作が評価される回数です。内側のループ内に 3 つの操作があるため、n 項目の操作の総数は 3 * n*(n-1)/2 になります。次の部分 (3/2)n^2-(3/2)n のために簡単な形に書き直します。

ステップ2

これで関数ができました。ここで、f() はアルゴリズムによって実行される操作の数 f(n) = (3/2)n^2-(3/2)n です。明らかに、最も急速に増加する項は (3/2)n^2 なので、(3/2)n を削除します。これにより (3/2)n^2 が残り、(3/2) 係数が取り除かれます。これにより、n^2 が残ります。したがって、f(n) は O(n^2) であると言えます。

これは基本的に、アルゴリズムを O() 表記で記述するためのレシピです。これは重要な理由を無視し、答えを生み出すための頭のないレシピを説明しています。なぜこのようにアルゴリズムを要約するのですか? 項や係数を単に忘れてよいのはなぜですか? これらの質問に対する答えは、より厳密な教科書の説明に記載されています。

ひどい間違いを犯していないことを願っています。少し遅れています。

于 2013-08-25T06:59:30.360 に答える
0

まず、次の方法でこの種のことを学ぶことができます。

  • アルゴリズムを説明し、その複雑さを分析するテキストブック (または研究論文、またはその他のリソース) を読む、または

  • 自分でアルゴリズムを分析します。つまり、数学をやっています。

十分な経験を積むと、アルゴリズムの複雑さを見積もるための直感的な近道をいくつか見つけることができます。

問題サイズの変数 (または変数) の値の範囲にわたってパフォーマンスを測定し、それらをグラフ化し、曲線を当てはめようとすることを一部の人が提案する手法の 1 つです。ただし、これには次のような問題があります。

  • 多くの場合、変数が実際に何であるかを知ることは困難です。
  • 多くの場合、変数間の関係が非常に複雑であるため、信頼性の高い曲線近似は不可能です。
  • 多くの場合、有効な (つまり、代表的な) 測定値を取得することは困難です。
  • 一部のアルゴリズムは、最良のケース、平均的なケース、および/または最悪のケースの動作に対して異なる複雑さの尺度を持っています。

つまり、このアプローチでは信頼できる答えが得られないことがよくあります。

于 2013-08-25T05:49:07.807 に答える