多次元ハッシュの空間複雑度

Question

C1、C2、C3、C4と言うと、データの列を表し、N行のデータがあるタブ区切り値の入力を保存したいとします。もしそうなら、私は、C1、C2、C3、C4のいくつかの指定された値が存在するかどうかを調べるためにハッシュのルックアップを行うことができます。誰かが、最悪の場合、この空間の複雑さはN であると私に示唆しました。なぜそうでないのかについて明確な説明をするのを助けたいと思います。

Answer 1

N人のポイントグリッドを保存しようとすると、N ポイントが保存されることになります。

しかし、Nポイントがある場合、ハッシュを保存するだけです。また、N個のデータポイントを持つハッシュには、通常、O（N）個のスペースが必要です。 （技術的には、ハッシュテーブルのサイズにデータのスペースを加えたサイズが必要ですが、通常、ハッシュテーブルのサイズは、データセットと同じオーダーのサイズになるように動的に調整されます）。