13

正と負の両方の整数を持つ無限長の並べ替えられた配列が与えられます。その中の要素を見つけます。

編集
配列内のすべての要素は一意であり、配列は正しい方向に無限にあります。

次の 2 つの方法があります。

アプローチ 1:

インデックスを 100 の位置に設定します。見つかった要素が小さい場合は、前の 100 項目でバイナリ検索を行います。それ以外の場合は、次のインデックスを 200 の位置に設定します。このようにして、項目が大きくなるまでインデックスを 100 ずつ増やし続けます。

アプローチ 2:

インデックスを 2 のべき乗で設定します。最初にインデックスを 2 の位置に設定し、次に 4、8、16 の順に設定します。再度、2^K から 2^(K + 1) までの二分探索を実行します。

最良の場合と最悪の場合の両方で、2 つのアプローチのどちらが優れているでしょうか?

4

8 に答える 8

25

最初のアプローチは、要素のインデックスで線形になります（O(k)ここkで、は要素のインデックスです）。k/100実際には、検索された要素である。よりも大きい要素を見つけるために反復が必要になりますO(k)。

2番目のアプローチは、同じインデックスの対数になります。O(logk)。（ここkで、は要素のインデックスです）。log(k)ここでは、より高い要素が見つかるまで反復が必要になります。2^(i-1)次に、2^i（iは反復回数）の間の二分探索も対数になり、合計するとO(logk)

したがって、2番目の方が効率的です。

于 2012-09-06T13:15:46.910 に答える
3

わずかな変更を加えるだけで、多かれ少なかれ直接二分探索を適用できます。これは、アプローチ2にほぼ対応します。

基本的に、いくつかの番号Bを選択し、Aを0に設定してから、探している要素がAとBの間にあるかどうかを確認します。そうである場合は、これらの境界で通常の種類の二分探索を実行します。そうでない場合は、B=AとAに設定します。 = 2*Aと繰り返します。これはO（log（M））を取ります。ここで、Mは配列内で探している要素の位置です。

于 2012-09-06T13:15:22.783 に答える
3

配列が十分に根拠がある場合、つまり最小の要素がある場合（つまり、要素x 0、x 1 、...がある場合）、すべての要素が一意である場合、次の簡単な方法があります。数値nを探している場合、インデックス0、...、n  −x0 に対してバイナリ検索を実行できます。すべてのi≥0に対して、常に基本的な不等式xi≥i +  x0 があることに注意して ください 。 

したがって、値nはlog 2（n  −  x 0）ステップで見つけることができます。

于 2012-09-06T13:23:22.867 に答える
2

配列は無限であるため、インデックスは必然的に可変長になります。つまり、それらに対して計算を行うのは ではありませんO(1)。つまり、「最初にエンドポイントを検索するバイナリ検索」は、 とは時間の複雑さがわずかに異なりO(log(k))ます。

エンドポイントの検索で行われるインデックス計算は、1 だけ左にシフトするだけです。これはO(log(k))、最大 までのインデックスkが最大ビット数を必要log(k)とし、左に 1 シフトすることはビット数に比例するためです。

二分探索で行われるインデックス計算O(log(k))も同様です。

したがって、両方のアルゴリズムの実際の複雑さはO(log(k)^2). 線形検索の複雑さは になるO(k log k)ので、それでも負けます。

于 2012-09-07T16:55:23.613 に答える
0

ちょうど私の2セント。無限の配列があるので、非常に大きな数を探していると想像してみましょう。想像しましたか？まあ、それはずっと大きくなっています。バイナリ検索までの間隔の長さは、2^i = 2^(i+1)-2^iしたがってlog(2^i)=i、数を見つけるのに時間がかかることに注意してください。一方でi、目標間隔に到達するには時間がかかります。したがって、総時間の複雑さはO(n)再び です。私は何が欠けていますか？

于 2012-09-07T05:56:40.157 に答える