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

Question

C1、C2、C3、および C4 がデータの列を表し、N 行のデータがある場合、タブ区切りの値の入力を保存したいと思います。もしそうなら、ハッシュを調べて、C1、C2、C3、C4 の特定の値が存在するかどうかを確認できます。誰かが私に、最悪の場合、これの空間複雑度は N ⁴であると提案しました。なぜそれが真実ではないのかについて、明確な説明を作成する手助けをしたいと思います。

Answer 1

他の人は、N x N グリッドのポイントを格納しようとすると、N ⁴個のポイントが格納されると考えています。

しかし、N 個のポイントがある場合は、ハッシュを格納しているだけです。また、N 個のデータ ポイントを持つハッシュは通常、O(N) 個のスペースを必要とします。(技術的には、ハッシュ テーブルのサイズにデータ用のスペースを加えたサイズが必要ですが、通常は、ハッシュ テーブルのサイズを動的に変更して、データ セットと同じ桁数のサイズにします。)