私は友人と宿題をしようとしていますが、1つの質問ではリニアプロービング方法の検索、追加、削除の平均実行時間が尋ねられます。私はO（n）だと思う。なぜなら、追加するオープンなものが見つかるまで、特定の数のノードでチェックしなければならないからだ。そして、それを検索するとき、それは元のインデックスから始まり、所望の数が見つかるまで上に移動する。しかし、私の友人はそれがO（1）だと言います。どちらが正しいですか？ハッシュコリジョンリニアプロービング実行時間
漸近的複雑さについて話すとき、私たちは一般に非常に大きなnを考慮に入れます。ハッシュテーブルにおける衝突処理のために、いくつかの方法は連鎖ハッシング&リニアプロービングである。どちらの場合も、あなたの質問に答えるのに役立つ2つのことが起こる可能性があります。1.ハッシュテーブルがいっぱいになったため、ハッシュテーブルのサイズ変更が必要になることがあります。
最悪の場合は、ハッシュテーブルをどのように実装しているかによって異なります。線形プロービングでは番号を見つけられず、移動し続け、探していた番号が最後に表示されます。ここでO（n）最悪の場合の実行時間が来る。連鎖的なハッシング技法になると、衝突が発生したときにそれらを処理するために、キーがバランスの取れたバイナリツリーに格納されているため、最悪の場合の実行時間はO（log n）になります。
今は最高のケースランニングタイムになる、私は混乱がないと思う、どちらの場合でもO（1）だろう。
O（n）は、最悪の場合に起こり、良好に設計されたハッシュテーブルの平均的なケースでは起こりません。これが平均的なケースで起き始めると、ハッシュテーブルはデータ構造内の場所を見つけることができません。なぜなら平均的な平衡ツリーはあなたにO（log n）を常に与え、その上にその順序を保持するからです。
申し訳ありませんが、残念ながらあなたの友人は正しいです。あなたのケースは最悪の場合のシナリオで起こります。
また、すなわち償却走行時間より有益なもののためここを見て：Time complexity of Hash table
ありがとう@DanAllen、上のあなたのコメントは本当に動機づけています:) – Yavar
私はYavarの答えに追加したい：Oは、（1）1個のオペアンプではないことを、覚えておいてください。これは大きな定数ですが、nのような変数から派生していないかどうかは関係ありません。ハッシュを配置するために20ノードを通過する必要があるとしても、それはまだO（1）です。もちろん、いくつかの条件が当てはまる場合にのみハッシュテーブルで動作しますが、平均的にO（1）であるうまく設計されたハッシュテーブルの場合 – Archeg