それで、私は二分探索についてもっと理解したいのです、なぜなら私は本当に理解していないからです。二分探索には、配列がソートされるという前提条件が必要です。正解ですか？メソッドはこの前提条件をチェックし、満たされない場合は例外をスローする必要があるようです。しかし、なぜ前提条件をチェックするのは悪い考えなのでしょうか？
2019 次
6 に答える
8
データが並べ替えられていることを確認するにはn手順が必要なので、これは悪い考えです。検索全体はlog(n)ステップに関するものです。
チェックする場合は、線形検索を実行することをお勧めします。
于 2009-10-17T21:08:28.610 に答える
7
二分探索の要点は、データがすでに並べ替えられているため、必要な情報をすばやく見つけることができるということです。
家系の名前でソートされた電話帳を取ります。
電話帳で誰かをどうやって見つけますか？あなたはそれをあなたが望むものに近いと思うページまで開いて、それからページをめくり始めます。
しかし、毎回1ページをめくるわけではありません。多くのページを見逃した場合は、たくさんのページをめくり、最後に1ページずつめくり始め、最後に1ページをめくります。
これは二分探索が行うことです。データは並べ替えられているので、多くをスキップして別の外観を実行できることがわかっており、必要な情報に焦点を合わせます。
二分探索は、アイテムの2倍の数ごとに1つの比較を行います。したがって、1024要素のコレクションでは、情報を見つけるため、または少なくともそこに情報がないことを理解するために、最大で約10回の比較が必要になります。
実際のバイナリ検索を実行する前に、データが並べ替えられているかどうかを確認するために完全なランスルーを実行する場合は、情報のスキャンを実行することもできます。フルランスルー+バイナリ検索にはN+log2 Nの操作が必要になるため、1024要素の場合は約1034の比較が必要になりますが、情報の単純なスキャンには平均して半分の512が必要になります。
したがって、データが並べ替えられていることを保証できない場合は、単純なスキャンよりもパフォーマンスが優れているため、バイナリ検索を使用しないでください。
編集：私はこれを言いますが、これを検証するためにデバッグのみのコードステップを追加して、バイナリ検索用のデータを準備することになっているコードのバグをキャッチすることができますが、私が上に書いたことにより、それを知っています、これにより合計実行時間が大幅に長くなるため、このチェックで何をしたいかに応じて、追加する場合としない場合があります。ただし、リリースコードには含まないでください。
于 2009-10-17T21:11:27.653 に答える
3
はい、バイナリ検索には0（log n）ステップが含まれ、シーケンス全体がソートされていることの確認には0（n）ステップが含まれます。私の観点からは、RELEASEではなく、DEBUGモードで検証することをお勧めします。
于 2009-10-17T21:11:08.210 に答える
1
二分探索は、入力データがソートされていることを前提としています。だからここであなたは正しいです。
ここで、一般的に、データがいつかソートされているかどうかをチェックします。したがって、すべての検索の前にこれを実行すると、検索が非常に非効率になります。
詳細。
'n'がデータの量であると想定します。
二分探索O(log(n))では、最悪の場合、要素を見つけるための操作が必要です。データがソートされていることを確認するには、O(n)操作が必要です。
したがって、非常に大きな前提条件を毎回チェックする場合n、実際の検索よりも前提条件のチェックにほとんどの時間を費やし始めます。
そして、いつそのような効果が見られるかを言うのはそれほど難しいことではありません。事前のチェックと実際の検索に費やす時間を計算しました
- 1つの要素については、検索に時間を費やすことはありません。
- 2つの要素の場合、検索に50％を費やします。
- 5つの要素の場合、検索に46％を費やします
- 20の要素の場合、検索に22％を費やします。
- 100個の要素の場合、検索に7％を費やします。
等々。いずれの場合も、時間の残りは前提条件のチェックに費やされます。
于 2009-10-17T21:09:45.053 に答える
0
実行時間について他の人が言ったことに加えて（すべての項目をチェックするためのO（n）と、バイナリ検索を実行するためのO（log（n）））。
前提条件の考え方を誤解していると思います。前提条件と事後条件は契約です。前提条件が真で、アルゴリズムを実行すると、事後条件が真になります。前提条件がfalseの場合、事後条件を保証するものではありません。
つまり、基本的に、バイナリ検索では次のようになります。提供されたデータがすでに並べ替えられている場合は、およそlog（n）チェックを実行することで、特定のデータの位置を知ることができます。データがソートされていない場合、私は自分の答えについて保証しません。
アルゴリズムの場合、事前条件から事後条件に移行する作業。この場合、二分探索。
于 2009-10-17T21:17:10.397 に答える
0
元の質問は、データのコレクションに対してバイナリ検索を使用していることを前提としています。常にそうであるとは限りません。多くの場合、ある間隔で数値を計算しようとしているだけです。
ファンの最適な速度設定を計算しようとしているとします。何らかの理由で閉じた形の式が見つからないため、さまざまな速度設定で気流をシミュレートします。
ファンが0RPMから5000RPMまでの任意の速度で動作できると仮定すると、実際に可能な速度のリストを生成する必要はありません。二分探索の各ステップで、前の最小値と最大値の平均を見つけるだけです。
于 2009-10-17T22:19:38.727 に答える