0

順次検索の場合、ファイル内のレコードを見つけるために必要な比較の平均数はいくつですか？

4

3 に答える 3

3

順次検索はファイルの先頭から始まり、目的の要素が見つかるまで各要素を1つずつチェックします。検索しているレコードがファイル内に1回だけ存在し、同じ確率でファイル内のどこにでも存在する可能性があると仮定すると、比較の平均数はファイル内のレコード数の半分に等しくなります。

ただし、レコードがファイルに存在しない場合は、これを検出する前に、ファイル内のすべてのレコードを調べる必要があります。

于 2010-03-06T17:24:27.570 に答える
1

n個のアイテムを含むリストの場合、最良のケースは、値がリストの最初の要素と等しい場合です。この場合、1つの比較のみが必要です。最悪のケースは、値がリストにない場合（または、リストの最後に1回だけ発生する場合）です。この場合、n回の比較が必要です。

したがって、漸近的に、線形探索の最悪の場合のコストと予想されるコストは両方ともO（n）です。

于 2010-03-06T17:30:11.227 に答える
0

前の回答が指摘できなかったいくつかのポイントを追加したいと思います。

  • 一方、ファイルが1つのデバイスで利用できるのか、複数のデバイスに分散しているのかを検討する必要があります。T ramsの場合、複雑さはになりますO(T*N/(1+log(T)))。

  • 一般に、順次検索にはがかかりますO(N) time complexity。

  • R-Treeなどのデータ構造と組み合わせるとO(N/(log(log(N))))、ファイル内のレコードの場合のベストケースの時間計算量を得ることができます。

  • データフィールドがハッシュマップで利用可能な場合、順次検索がバックログになるように、ファイルの構造/形式によって異なります。

于 2017-06-15T05:22:12.570 に答える