algorithm - 時間計算量が最小の検索アルゴリズム

Question

時間計算量O（1）の検索アルゴリズムはありますか？

検索アルゴリズム=n個の要素から要素xを検索します。

Answer 1

決定論的に O(1) である検索アルゴリズムが存在する場合は驚くでしょうが、良いニュースは、ブルーム フィルターを使用した O(1) の加算およびルックアップ操作で、100% に近い任意の精度のルックアップを取得できることです。(http://en.wikipedia.org/wiki/Bloom_filter)

同様に、有限サイズのセットにはさまざまな手法が存在します (http://en.wikipedia.org/wiki/Perfect_hash_function) が、これらのセット サイズが非常に大きい場合、実際には問題が発生します。

しかし、一般的なケースでは、私の知る限り、答えはノーです。そして確かに、実際のアプリケーションではありません。

Answer 2

はい、巨大な配列を作成して、可能な値ごとに 1 つのスロットを持つようにします。値の格納と値の検索の時間計算量は O(1) です。

編集：

初期化時間もカウントされる場合、O(1) 検索アルゴリズムを作成することは絶対に不可能です。前処理なしで配列を検索することは、O(n) よりも優れていることはありません。また、O(1) で n 個の項目を前処理する方法はありません。