- ベストアンサー
逐次検索と平均比較回数について学びたい初心者です
- アルゴリズムの解析を勉強している初心者です。
- n個の配列における逐次検索の平均比較回数の計算方法について教えてほしいです。
- 探したいindexがn/2までを考慮する必要があるのか知りたいです。
- みんなの回答 (3)
- 専門家の回答
質問者が選んだベストアンサー
アルゴリズムの比較回数については "指数" の部分が重要になってきます。 nをデータ数としたとき n , nの2乗 , nの3乗 それぞれ n にどんな値が入ったところで各々の差が莫大であることは明らかです。 これに次元数の違う値を足し引きしたところでこの差は対して埋まることはありません。 例) nの3乗 , nの3乗 + nの2乗 n = 100のとき nの3乗 = 1000000 , nの3乗 + nの2乗 = 1001000 対して差がありませんね。 つまり、アルゴリズムの比較回数では "最大指数" のみを考慮します。 今回の問題の場合(定数は省いて考えます) 1番目の場合 2/n → 1/n 2番目の場合 {(n-2)/n*2/(n-1)}*2 → n/n/n → 1/n 3番目の場合 {(n-2)/n*(n-3)/(n-1)*2/(n-2)}*3 → n/n*n/n*n → 1/n 定数を省いた場合の計算結果は同じですね。 "だから2回目以降を無視しても良いのです" !を使って表現する場合 要素の出現回数をi,データ数をn とすると i!*(n-2)Pi/nPi と表現できます。
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
ついでにいうと, 平均比較回数が (n+1)/2 と「定義されている」ってこともないっす. あと, 「n個の配列に要素が2回出現した場合」の意味はよくわからん. 「要素」っていうのは「探したい要素」のこと? 「2連続で要素が出現することもありません」という仮定がなぜ必要なのかも不明.
- salsberry
- ベストアンサー率69% (495/711)
投稿先のカテゴリはJavaで合っていますか? また、 > 平均比較回数は、(n+1)/2と定義されています。 とか > 探したいindexが 4 だとすると とか書かれていますが、その配列に対して何をする話なのか、そもそもの前提の部分が抜けているため課題の内容が分かりません。 タイトルに「逐次検索」とあるので、ある値が配列の中に入っているかどうか、入っているのであれば何番目の要素なのかを求める話なのだろうなと想像はできますが。