私は未ソート配列の連続検索アルゴリズム持っアルゴリズム

の平均場合の複雑見つける：私はことを知っている私たちは入力配列A[0...n-1]と検索キーK私は未ソート配列の連続検索アルゴリズム持っアルゴリズム

を持って

SequentialSearch(A[0..n-1],K) 

i=0 
while i < n and A[i] != K do 
    i = i+1 
if i < n then return i 
else return -1

を最悪の場合はnです。なぜなら、配列全体を検索しなければならないからです。O(n)

ベストケースは1であることがわかります。 chは私たちが望むもの、または配列に同じアイテムを持っていますO（1）

しかし、私は平均の場合を計算する方法については考えていません。私の教科書が与える答えは次のとおりです。

= (p/n)[1+2+...+i+...+n] + n(1-p)

私はそれを計算するために、この1のようなアルゴリズムを見たときのために続くことができる一般式はありますか？あなたが入力例を検討する必要があると思い Textbook example

出典

2017-02-17 o4o42o3k2o

編集：私は解決策を示して追加した画像を確認し、私はちょうど彼らがそれを取得しているのか分かりません。 – o4o42o3k2o

https://en.wikipedia.org/wiki/Linear_search –

@ミッチコムギ、正確に。私の答えは、あなたがリンクしたエントリーと一貫しています。どうやら誰かが衝動的に投票しました。 –

BELOW

は

PICTURE、アルゴリズムの文脈に依存した入力の等価クラス、のようなもの。それらの事柄のどれも知られていない場合、入力がランダムな整数の配列であると仮定すると、平均の場合はたぶんO（n）になります。これは、おおよそ〜32k〜32kの範囲のN個の整数値の配列でクエリがどれくらいの頻度で有用であるかを証明する方法がないためです。ここ

出典

2017-02-17 01:34:23

私は画像を追加しましたが、それはO（n）にすることはできません。平均的なケースを得るプロセスについてはわかりません。 – o4o42o3k2o

そうですが、教科書はどのように答えを得ていますか？私はそれらの合計を理解していないどこから来たのですか？私がこのようなことでテストされたら、彼らが何をやっているのかを再現できる必要があります。そして、私はよく分かりません。 – o4o42o3k2o

それは確かに混乱の表記です。確率がどのように関係しているのかを理解するために、他の情報源を見てから、テキスト記法を解析しようとします。 –

= (p/n)[1+2+...+i+...+n] + n(1-p)

pたちはn要素を持っているので、我々はn内の特定のインデックスにキーを発見する確率としてp/nを持って、アレイ内で見つかった検索キーの確率です。我々は本質的に各繰り返しのように加重平均を行い、1回の比較、2回の比較、およびn回の比較までに重み付けをする。すべての入力を考慮する必要があるため、2番目の部分n(1-p)は、配列1-pに存在しない入力の確率を示します。配列全体を検索するにはnが必要です。

出典

2017-02-17 02:40:15

より形式的には、Xは、スキャンする必要がある配列Aの要素の数を表す離散的なランダム変数であるとします。 n要素があり、ランダムに生成された入力に対してすべての位置が均等になるため、の場合は（確率でp）の配列に検索キーがあると、）。したがって

、x = 1,..,nためP(X=x)=(1/n).p.I{x<n}+((1/n).p+(1-p)).I{x=n}、I{x=n}は、インジケータ関数であり、そうでなければx=n0ときに限り値1を有するであろう。

アルゴリズムの平均複雑度は、入力が任意のシーケンスであるときにアルゴリズムを実行するのに要する予想時間です。定義によると、