ハッシングの複雑さ（最悪の場合）

1）n要素を持つ線形リストに要素を挿入する最悪の場合。ハッシングの複雑さ（最悪の場合）

2）n個の要素とb個のスロットを持つハッシュテーブルに要素を挿入する最悪のケース。各スロットはソートチェーン（一部のスロットは空の場合があります）です。

私は（1）はO（n）だと思いますが、何が（2）なのか分かりません。

2016-11-02 Samin Khan

これらの時間の複雑さを見つけるときに任意のコードを参照していますか？それは、これらのこととその理由を理解するのに大いに役立ちます。 – 4castle

私はあなたがより質の高い質問をすることができるように、最初にいくつかの研究を行うことをお勧めします。 – 4castle

ハッシュテーブルに挿入するのは平均的なケースO（1）です。最悪の場合は、テーブル内のすべての値が同じハッシュ値で衝突するため、すべての要素が同じスロットにあるため、挿入時間はソートチェーンの場合と同じになります。 – 4castle

（2）の最悪ケースもO（n）です。これは、ハッシュ内のn個の要素（またはそれらのうちの少なくとも一部）が特定の1つのスロットで終わる可能性があり、この新しい要素がそのスロットに再度マップされるためです。したがって、新しい要素をサイズnのソートされたリストに挿入する必要があり、これは他の要素をシフトする必要があり、結果としてO（n）になります。

しかし、ハッシングの人々は通常、最悪の場合の動作ではなく平均的な動作を心配しています。

出典

2016-11-05 21:09:43

ありがとうございました。 –

@SaminKhan問題ありません。この回答が満足だと思うなら、それを最善の答えとして受け入れてください。 –

ハッシングの複雑さ（最悪の場合）

答えて

関連する問題