バイナリ検索の時間の複雑さを理解しようとしています

-1

私は、バイナリ検索の時間の複雑さについてBig O表記を理解しようとしています。私はそれがO（ログn）であることを理解しています。これは、基本的に、16個の要素のリストに対して、最大でlog2（16）= 4回の試行をとると言っていますか？もしそれが本当であれば、log = 3.6の12のリストに対してどのように動作しますか？バイナリ検索の時間の複雑さを理解しようとしています

おかげ

出典

2017-05-17 Sam Sims

はビッグああ表記法の有用性は、それが特定のサイズの入力を処理するのにかかる正確にどのように多くの操作を指示することができないです。それはできません。

ビッグ-OH表記は処理を行うために必要な操作の数は、入力サイズに関係にどのように変化するかを教えてくれる。

したがって、実際の数値を代用することはあまり意味がありません。

実際の数字の点で理解するのが本当に助けになるならば、それらを平均と考えることができます。したがって、12の要素のリストでは、平均3.6の操作を必要とするバイナリ検索と考えることができます。

しかし、これはビッグオーバ表記のすべてについてのかなり狭い見方であることに注意してください。 big-oh表記法の本当の有用性は、バイナリ検索が線形検索よりも優れているということです。特定の具体例が必要とする操作の正確さを私たちに教えてくれるわけではありません。

出典

2017-05-17 18:02:16

ああ、入力数が増えるにつれて操作数が対数的に増え、数字について心配しないと言われていますか？ –

正確に。実際の数値は詳細なものであり、操作がマシンに対して表す実際のコストも同様です。マシンが関与する限り、バイナリ検索での1つの演算は、アルゴリズムがより複雑であるため、線形探索での1つの演算より実際には多くのクロックサイクルを要します。しかし、それは重要ではありません。なぜなら、より大きい入力セットを調べ続けると、各操作を非効率的に実行するかどうかにかかわらず、バイナリ検索が線形検索よりもパフォーマンスが向上し始めるからです。それは大きなああの美しさです。 –

また、私はあなたの質問をdownvoting人々に気づきます。あなたが失望しないように、ポスターを質問する前にいくつかの調査をすることが期待されていることと、大口に関するすべてがかなりよく文書化され、比較的簡単にアクセスできるという意見が多いからです。（ウィキペディアを参照してください）しかし、私は毎日ここに見る他の質問で判断すると、あなたのことはそれほど悪くはありません。 –

バイナリ検索の時間の複雑さを理解しようとしています

答えて

関連する問題