ハッシュテーブルの複雑さ

Question

ハッシュテーブルのベストケース、最悪ケース、平均ケースを把握しようとしています。 ハッシュテーブルサイズm、入力nサイズ。

1. 衝突が存在する「平均」のデータとハッシュ化された電話帳に名前を見つけることが、リニアプロービングは、衝突解決 スキームのですか？
2. 衝突解消のために線形プロービングを使用するハッシュテーブルでk番目のargest項目を見つける？
3. 衝突解消のために別々の連鎖を使用するハッシュテーブルでk番目に大きなアイテムを見つけるか？

マイ回答： 1.ベスト：1最悪：Mの平均：M/2 2.ベスト：1最悪：Mの平均：M/2 3.ベスト：1最悪：1 + nは平均： （1 + 1 + n）/ 2 = n？

ADT（Tree、Hash、Array）のいずれかの特定の要素の検索が常に1であると思っていた。何とか魔法のようにO（1）で必要なものを見つけたので、ちょうど最悪+ベスト/ 2です。そうですか？

私の考えが間違っている場合は、私を修正してください。

Answer 1

1. ワーストケースO（n）。この値に達する前に自由な場所に足を踏み入れることはないので、n個のプローブがそこに存在できるので、入力サイズです。 平均ケースと最良ケースO（1）。

k番目に大きい項目は、k番目に大きいキーが存在する場合です。

2. 最悪の場合：O（kn）平均と最悪の場合：O（k）。

3. 最悪の場合：O（kn）平均と最高の場合：O（k）。