なぜO（1）時間内に検索/挿入/削除できないのですか？

-2

O（1）時間内に検索/挿入/削除をサポートできるデータ構造がないのはなぜですか？なぜO（1）時間内に検索/挿入/削除できないのですか？

2016-05-10 Naomi

あなたの質問には欠陥があります.O（1）時間に検索、挿入、または削除するデータ構造を持つことができます。例えば。リンクされたリストを使用すると、O（1）時間内に挿入と削除が可能になります。ポインタを変更するだけです。配列を使用すると、O（1）時間内に配列インデックスで検索できます。 –

いいえ、すべての検索/挿入/削除機能でO（1）時間をサポートできるBST O（log n）、Bツリー、またはフィボナッチヒープのようなデータ構造がないのはなぜですか？ – Naomi

@ Naomiもし数学的証明を求めているなら、非常に正確な質問をしなければならないでしょう。 O（1）でツリーが動作できない理由を知りたいですか？複雑さを計算するアルゴリズムはありますか？また、実際には、O（1）の挿入/削除用のデータ構造を作成するのは非常に簡単です。問題は、メモリの複雑さが急速に増加する可能性があることです。 – Sulthan

ハッシュ関数は、ハッシュ関数が適切に設計されている場合、平均してO（1）で動作します。もちろん、最悪の場合、ハッシュテーブルはO（n）である。ハッシュ関数がすべての要素に対して同じ値を返す場合

出典

2016-05-10 11:34:03

あなたはそれを詳述できますか？ – Naomi

数学的証明のために、我々は通常、ハッシュ関数が一様であり、入力がランダム化されていると仮定する。また、ハッシュ関数をランダムに選択すること（普遍的なハッシュ）もあり、不正なデータを防ぐことは非常に一般的です（ランダムなクイックソートに似ています）。その場合、漸近的複雑さは実際には0（1）です。 – Sulthan

なぜO（1）時間内に検索/挿入/削除できないのですか？

答えて

関連する問題