ハッシュテーブルO（1）償却またはO（1）平均償却？

Question

この質問は少し賢明かもしれませんが、私は本当に償却分析に深く浸透しようとしていますが、なぜハッシュテーブルの挿入がO（1）償却されているのか混乱しています。

この定義を使用すると、「償却分析は、最悪の場合の各操作の平均パフォーマンス（時間をかけて）を示します」。ハッシュテーブルへのN個の挿入が最悪の場合のように、すべての操作で衝突が発生するようです。ユニバーサルハッシングは、負荷バランスが低く保たれているときに1/mのレートで衝突を保証しますが、理論的にはすべてのインサートに対して衝突を起こすことはまだ可能ではありませんか？技術的に平均は、ハッシュテーブルの挿入のための分析を償却ように思え

はO（1）です。

編集：ハッシュテーブルは、対応するリンクリストの最後に要素が配置されている基本チェーンを使用すると想定できます。私の疑問の真実は、確率論的アルゴリズムの償却分析を指しています。

編集2： 私は 「もそこ償却走行時間の間に微妙だが重要なディのFFレンスだと時間を実行している期待、クイックソートのthisポストを見つけランダムなピボットとクイックソートはO（n個のnを記録）時間を実行している期待がかかりますが、その。最悪の場合の実行時間はΘ（n^2）です。これはクイックソートが（n^2）ドルの費用を払う可能性は低いですが、nが大きくなるとゼロに近づく確率が低いことを意味します。これはおそらく私の質問に答えると思う。

Answer 1

理論的には、挿入ごとに衝突が発生する可能性がありますが、パフォーマンスが悪いハッシング関数を使用しているため、キーの「バケット」の値の範囲を限定できませんでした。理論上完全なハッシュ関数は常に新しいバケットに新しい値を入れて、各キーがそれ自身のバケットを参照するようにします。 （私は連鎖ハッシュテーブルを想定しており、連鎖フィールドを「バケツ」と呼んでいます、ちょうど私がどのように教えられたか）。理論的に最悪の場合、すべてのキーを同じバケットに張り付けることで、長さNのバケットのチェーンにつながります。

償却の背後にあるアイデアは、合理的に良好なハッシュ関数が与えられれば、挿入が> O（1）である回数は、挿入が単純でO（1）である回数が大幅に少なくなるため、挿入してください。それは挿入が計算なしであると言うことではありません（ハッシュ関数はまだ計算されなければならず、特別なケースではハッシュ関数は単にリストを見ているよりも計算量が多いかもしれません）。

これは、時間の複雑さを計算するときに最も頻繁に実行されるアクションを調べる必要があるという考えであるbig-Oの重要な概念につながります。この場合、それは別のハッシュと衝突しない値の挿入です。