私は、-10から-43の範囲で比較的均一に広がる2倍のソートされた配列（実際には緯度）を持っています。さて、私はそのリストをバイナリ検索した場合、私はO（ログN）を取得します。私の検索はどのようなBig-O方程式で記述されていますか？
しかし、34個のキー（-10〜-43）があるルックアップテーブルを持つことで、検索によってさらに最適化できます。このキーは、その番号の始点に直接ジャンプできます。
例：-23.123424最初にルックアップキー23を押し、すべての-23の値の開始範囲を確認します。私はその中間からバイナリ検索をすることができます。
私のBig-Oの外観はどうですか？
まだO（ログn）です。考えてみましょう：整数ルックアップテーブルの開始インデックスを検索するために一定の時間がかかるため、パーツに何も追加されません。次に、バイナリ検索を行うにはO（log n）です。実際には、平均で34倍小さい配列を検索することを期待しているため、実際にはn/34をログに記録します（値は-43から-10の境界で34の異なる間隔で分散されます）。しかし、定数乗数は大きくは考慮されません-O表記。
そしてlog（n/34）= log（n） - log（34）。だからここに定数乗数はありません。 –
@AdamMihalcinあなたは大丈夫です！ – Celada
あなたの最適化が役に立ちそうですが、正確な値を検索する必要があるため、まだO（ログN）と考えられています。値に直接かかった場合はO（1）
これはBig-Oh分析の限界です。あなたが検索しなければならない価値の量を減らしたことを考慮に入れていません。
確かですが、最適化によって検索対象の要素数が漸近的に複雑になる場合にのみ違いがあります。 Big-Ohは実際にアルゴリズムに必要な操作の漸近数に過ぎません。 –
ただし、データセットが小さくなると（Nの値が小さいと考えられますが）、それでもなおO(log N)になります。
ルックアップテーブルはca. 1/34、つまりバイナリ検索の1/32または5ステップに近い場合は、これが本当に役立つ場合はベンチマークすることができます。キャッシュミスの多い追加コードパスと、分岐予測/パイプラインの間違ったコードパス直接バイナリ検索よりも遅くなる可能性があります。
さらに、メモリー内テーブルの参照時間がボトルネックである場合は、ラットをInt32の値で表現することを検討することをお勧めします。
速度以外にも、角度（緯度と経度を含む）のために浮動小数点の代わりに32ビット整数を使用するもう1つの理由があります。浮動小数点の場合、ゼロに近い値は精度が高くなります（小数点以下は無損失に格納されます）ゼロから遠く離れている。しかし、赤道に近いポイントを他のポイントよりも正確に格納する必要がある理由はありません。0は0を意味するようにスケーリングされた整数で、2147483648はπラジアンが固定小数点数と等価であり、このアプリケーションに適していることを意味します。 – Celada
私はそれを確かにします！大きな利益と私はすでにファイルにデータを生成しているので、私は32ビットに変換するだけです。非常に素晴らしい。 – peterept
@Celada Ofcourseあなたは正しいですが、実際の結果はほとんどないと思われます.OQのように-10と-43の間の値が浮動小数点精度を持つと疑われます。これはデータ（GPS？）よりもはるかに優れています。品質。また、データの起点は 'float'なので、再スケーリングは元のデータにはなかった新しい精度を導入しません。それにもかかわらず、私たちは「int」が行く方法であることに同意します。 –
コンセプトはinterpolation searchに近いですが、キーの不可欠な部分に1回だけ「補間」するのではなく、補間を使用して2分探索を知的に駆動します。ドメインは比較的均一なので、予想される実行時間はO(log log n)です。
コードでは次のようになります。私は-23.1234を持っていますので、「大まかに」-23のパーセントは-10から-43にジャンプします。私は値を見て、それが-33だと言う。だから私は今-10から-33の間で一定の割合でジャンプします。 – peterept
@peterept修正します。入力がより均一になればなるほど、あなたは正しいエントリにジャンプします。 –
[skip list]（http://en.wikipedia.org/wiki/Skip_list）のようなものを実現しようとしているようです。 –
@BrianRoachスキップリストにもO（ログn ）ルックアップの複雑さ。彼らの唯一の利点はバニラバイナリツリーとその自動バランシングプロパティです。 –