-4

アルゴリズムの時間の複雑さを計算する方法を忘れてしまいました。その知識をリフレッシュするために本や 30 ページのブログを探しているわけではありません。以下のアルゴリズムを使用して、時間の複雑さを計算する方法を修正してください。ありがとう

線形検索

bool SeqSearch(int[] arr, int sValue) {
    for (int index = 0; index < arr.Length-1; index++)
    if (arr[index] == sValue)
        return true;
    return false;
}

使用する手順とロジック

  1. すべての要素をループします -N
  2. 各インデックスの比較 -1またはそれはN
  3. true または false を返す -1

ついに

これらを合計するか、掛けるか忘れましたか？追加する必要があると思ったので、結局、 N+N+1これはビッグオーに違いありません！NのO(N)

質問

  1. 各ステップにかかった時間を掛けるか、足すか
  2. 比較のために、いつ終了するかを判断することはできません。それで、かかった時間は何ですか（最初のインデックスで見つかる可能性があるため1を想定し、それ以外の場合は最後のインデックスとしてNを想定しました）
  3. 課題と返却は一定時間 1 ?

注: ウェブサイトを参照しないでください。SOは長く続き、同じ/類似の質問を持っている人は、この投稿への回答が役立つと確信しています. 他のウェブサイトがいつ削除されるかなど信頼できません。また、効率や時間の複雑さについては気にしていませんが、それを見つけるために使用されるプロセス/手順については気にしていません。

リソース

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.pdf

どのステートメントといつを説明するかを明確に説明するこのリンクをpdfに貼り付けたかっただけです。私が欲しかったように。

4

1 に答える 1

5

プリミティブ操作 (メモリ アクセスと算術/論理演算) の観点から考えてください。

入力のサイズを考慮して、アルゴリズムのためにそれらを数えますN（arr.Lengthあなたの場合）。

次に、演算の総数が にどのように関係するNかを確認します。これは、定数、多項式N(たとえばN3 )、対数N、指数、Nまたはその他のものであるかどうかにかかわらずです。

N+1 や 2*のような結果になった場合は、が大きいN場合に何が起こるか、および全体的な動作に主に関心があるため、小さな定数を無視する必要があります。N

それが基本です。

最悪の場合 (が にsValueない場合) のおおよその時間計算量は次のarr[]とおりです。

int index = 0;は 1

index < arr.Length-1;arr.Lengthは 1 (ただし、たとえば 10まで可能)、繰り返し

index++arr.Lengthは 1 (ただし、たとえば 3まで可能)、繰り返し

if (arr[index] == sValue)arr.Lengthは 1 (ただし、たとえば 10まで可能)、繰り返し

return value;は 1

arr.Lengthしたがって、1 + 1 * + 1 * arr.Length+ 1 * arr.Length= 1 + 3 * + 1 のようなものがあります。これarr.Lengthを に単純化するとarr.Length、O( N) になります。

arr.Length平均して、反復は / 2 回しかありません。したがって、平均すると、 1 + 1 * arr.Length/ 2 + 1 * arr.Length/ 2 + 1 * arr.Length/ 2 + 1 = 2 + 1.5 *になりarr.Lengthます。繰り返しますが、O( N)。

しかし、あなたは本当にこのことについて読むべきです.

于 2012-06-23T05:55:00.783 に答える