9

私は非常に多くのリソースを読みましたが、時間の複雑さとは何かを理解するのにまだ苦労しています。私が読んだリソースはさまざまな式に基づいていてO(n)、それが時間の複雑さを表現するために使用されていることは理解していましたが、その方法はわかりません。誰かがこの原則を理解できる明確な方法で私に説明してください。

4

2 に答える 2

34

参考：時間計算量アルゴリズムの計算方法

任意のアルゴリズムまたはプログラムの時間の複雑さを計算する方法に関連する良い記事を見つけました

時間の複雑さを計算するための最も一般的なメトリックは Big O 表記法です。これにより、すべての定数要素が削除されるため、N が無限大に近づくにつれて、実行時間が N に関連して推定されます。一般的には、次のように考えることができます。

statement;

定数です。ステートメントの実行時間は、 Nに関連して変化しません。

for ( i = 0; i < N; i++ )
     statement;

線形です。ループの実行時間は N に正比例します。N が 2 倍になると、実行時間も 2 倍になります。

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

二次です。2 つのループの実行時間は、N の 2 乗に比例します。N が 2 倍になると、実行時間はN * Nだけ増加します。

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

対数です。アルゴリズムの実行時間は、N を 2 で割り切れる回数に比例します。これは、アルゴリズムが反復ごとに作業領域を半分に分割するためです。

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

N * log ( N ) です。実行時間は、対数的な N ループ (反復または再帰) で構成されているため、アルゴリズムは線形と対数の組み合わせです。

一般に、すべての項目を 1 次元で処理することは線形であり、すべての項目を 2 次元で処理することは 2 次であり、作業領域を半分に分割することは対数です。立方、指数、平方根などの Big O メジャーは他にもありますが、それほど一般的ではありません。Big O 表記は O ( ) と記述され、ここで は測定値です。クイックソート アルゴリズムはO ( N * log ( N ) ) と記述されます。

これは、最良、平均、および最悪の場合の対策を考慮していないことに注意してください。それぞれに独自の Big O 記法があります。また、これは非常に単純化された説明であることにも注意してください。Big O が最も一般的ですが、私が示したよりも複雑です。他にもビッグオメガ、リトルオー、ビッグシータなどの表記があります。おそらく、アルゴリズム分析コース以外では遭遇しないでしょう。;)

編集：

ここで問題は、どのようlog nにして方程式に入ったかです。

  1. 各ステップでは、前半と後半でアルゴリズムを再帰的に呼び出します。
  2. したがって、必要なステップの総数は、問題を各ステップで 2 で割ると、n から 1 に到達するのにかかる回数です。

式は次のとおりです。n / 2^k = 1. 2^logn = n であるため、k = logn が得られます。したがって、アルゴリズムが必要とする反復回数は O(logn) であり、アルゴリズムは次のようになります。O(nlogn)

また、大きな O表記により、計算が簡単になります。つまり、アルゴリズムが漸近的に (無限大で) どのように動作するかについてのプラットフォームに依存しない近似値です。これにより、アルゴリズムの「ファミリー」を複雑さのサブセットに分割し、それらを簡単に比較できます。

さらに読むために、この質問をチェックすることもできます:再帰方程式を使用したプログラムの時間複雑度

于 2013-04-26T09:13:28.717 に答える