1

いくつかの基本的で一般的なアルゴリズムに頭を悩ませようとしています..質問に対する私の現在の理解は太字です。

( 1 ) n 個の項目を持つソートされた配列があると仮定すると、二分探索は最大で何回要素を比較しますか?

このタイプの質問に対する一般的な回答として ' 0(log(n)) ' がポップアップ表示されるのを見続けていますが、その理由がわかりません。この質問に答える整数はありませんか (つまり、2 または 3?)

( 2 ) n 個の項目を持つ配列があると仮定すると、線形検索で要素を比較できるのは最大で何回ですか?

繰り返しますが、上記と同じですが、' 0(n) ' がこの質問に対する一般的な答えのようです。繰り返しますが、私はこの答えの背後にある力を本当に理解していません。なぜ整数の答えがないのですか?

( 3 ) 線形検索が二分検索よりも優れている場合の例を誰か説明できますか?

私が収集した情報によると、一般的には、可能であれば二分探索の方が優れているように思われます。線形検索がより適切なオプションになる場合を判断するのに苦労しています。

4

4 に答える 4

3

1&2に関しては、入力のサイズとして絶対数が指定されていれば、答えとして絶対数が可能でした。質問は任意のサイズの配列 (長さn) について尋ねるため、これらの用語で回答も与えられます。詳細については、大きな O 表記
について詳しく 読むことができますが、基本的に&はそれぞれ&を意味します。たとえば、入力サイズが 100 の場合、線形検索を使用して比較される要素の数も 100 のオーダーになりますが、二分検索を使用すると ~ log(100) 個の要素を比較する必要があります。 3に関しては、バイナリ検索では入力をソートする必要があります...O(n)O(log n)order of norder of log(n)

于 2015-05-03T15:29:25.430 に答える
1

O表記は、動作を制限することに関するものです。したがって、二分探索はリストを 2 つに分割します。アイテムを見つけたか、検索する必要があるかのどちらかです。したがって、O（nlogn）の制限動作-つまり、検索ツリーの葉で。

線形検索は最初から始まります。最悪の缶 (限界) は要素が最後にあります)。

(3) 項目がリストの最初にある場合は、大当たりです。だからその場合は良いだろう

于 2015-05-03T15:36:51.460 に答える
0

次のビデオは、包括的な説明を提供します。二分探索と線形探索の違いを理解するのに役立つことを願っています。

質問 3 の場合:

  • 二分探索には、ソートされたシーケンスが必要です。
  • シーケンス 1,2,3,...,100 の場合。要素 1 を検索する場合は、線形検索の方が高速です。最初の要素をチェックするだけです。
于 2015-05-03T15:41:18.690 に答える