配列がある場合、O（1）でトップ 'x'を見つけてください

Question

私はそれを見つけたので問題を書くつもりです。

"先生は0-10の間に生徒の仕事をマークしていますが、「n」生徒の特定の数字「x」（例えばx = 15）に8以上のマークしか付いていません。すべての生徒のマークがランダムな順序で配列されています.O（1）で「x」の最良のマークを探します。

私は確かにハッシュを教えてきましたが、これは必ずO（1）ではないハッシュテーブルにすべてのデータを格納する必要があります。たぶん、「コンバージョン」を考慮する必要はありませんか？もしそうであれば、おそらく検索時間と組み合わせた変換は、ハッシングとは異なる方法につながるでしょう。

この場合、O（1）を脇に置いておくと、変換と検索時間の両方を含む最も速いアルゴリズムは何ですか？

Answer 1

シンプル：不可能です。

O(1)は、入力サイズ、必要な比較数および出力サイズがすべて定数である場合にのみ達成できます。 xは定数として扱うことができると主張するかもしれませんが、それでも動作しません。

すべての入力要素、すべてnを検査する必要があります。ランダム入力順でヒューリスティックを推測することさえできないからですx要素は、たとえすでに一定時間内にもう1つのx-1要素を正しく推測していても同じです。

問題が述べられているので、上限のO(1)またはO(x)で解決できる解決策はありません。

---

のは、ちょうどあなたの講師は、彼のミスを修正し、あなたに正しく必要上限としてO(n)を述べて改訂版を与えると仮定しましょう。

その場合、ハッシュアプ​​ローチは（ほぼ）正しいです。ハッシュ関数を使用することのキャッチは、ハッシュ関数が潜在的に衝突する可能性を考慮する必要があることです。これは、ハッシュマップがO(1)では厳密には機能しませんが、O(1)では「平均」にすぎません。

すべての可能な値（0〜10のグレード）を知っているので、既知のインデックスを持つバケットを割り当てることができます。各バケットの内部では、一定時間の挿入と線形時間の繰り返しが可能なので、リンクされたリストを使用することもできます。