algorithm - 線形探索の平均的なケース

Question

要素 A1、A2、...、An の配列があります。

ユーザーが各要素を検索する確率は、P1、P2、...、Pn です。

要素が再配置された場合、アルゴリズムの平均ケースは変わりますか?

編集：試験に出た質問を投稿しました。

Answer 1

いいえ、配列内の要素にアクセスするには O(1) 時間がかかり、配列内のこの要素の位置に依存しないためです。したがってarr[0]、arr[10000]同じ時間がかかるはずです。

リンクされたリストやバイナリ ツリーのようなものがある場合は、アクセスされる可能性が高い要素を先頭に近づけることが理にかなっています。