二分探索を使用して配列内のn個のソートされた個別の整数すべてを見つけるために必要な比較の総数はいくつですか？数はnlog2 n （ 2が底）だと思いますが、よくわかりません。どう思いますか？
6960 次
5 に答える
3
正確な答えが必要な場合は、明らかにN log（N）またはN log 2 （N）ではありません。ほとんどの整数Nの場合、logNとlog 2は有理数ではありませんが、比較の数は整数値でなければなりません。
また、正確な答えは、二分探索アルゴリズムの実装の詳細によって異なります。たとえば、「比較」が真と偽を返す単純な関係である場合、「比較」が負、ゼロ、または正を返す場合よりも多くの比較が必要になります。（後者の場合、アルゴリズムがキーを早くヒットしたときに短絡する可能性があります。）
于 2010-04-07T06:43:22.233 に答える
1
log2 nそれぞれを見つけるのに時間がかかり、それはn何度も行われる必要があるので、そうn log nです。
于 2010-04-07T06:43:35.200 に答える
0
1 つの数値に対して、最大で (2 * log 2 n + 1) の切り捨て (7.6 => 7) の比較が行われます。
配列内のある数値にたどり着くと、まず、それが探している数値かどうかを確認します。(== 最初の比較)。その後、小さい (または大きい) かどうかを確認します (2 回目の比較)。
数値を見つけるには、最大で log 2 n の数値を処理する必要があります。
そして、最後の数値を比較して、これがその数値であることを確認する必要があります。
したがって、[1..16] で 16 を探すには、2*log 2 16 + 1 = 9 回の比較が必要になります (これらの数: 8、12、14、15、16 にたどり着くと仮定します)。[1..10] で 10 を探すには、2*log 2 10 + 1 = 7.6 => 7 が必要です (これらの数値にたどり着くと仮定します: 5、8、9、10)。
したがって、n 個の数の場合、多くても n 倍になります。
于 2010-04-07T08:33:41.373 に答える
0
あなたのコメントをありがとう、今私は明確です。スティーブン C の言ったことは本当だと思います。正確な値がなければ、この質問の式を実際に計算することはできないと思います. ただし、511(2^9 -1) のように n=2^n -1 の場合、計算は簡単です。511 の場合、比較の総数 = 1x1 + 2X2 + 3X4 + 4X8 + 5X16 + 6X32 + 7X64 + 8X128 + 9X256 = 4097。
于 2010-04-07T17:26:09.250 に答える
0
私はそれがかかると言うでしょうn log m
ここで、m は配列のサイズなのでlog m、値を見つけます。そしてn、n個別の整数に対してこれを行います。
合計n log mで。
于 2010-04-07T07:29:32.573 に答える