Пространственная сложность многомерного хэша

Question

Я хотел бы сохранить ввод значений, разделенных табуляцией, где, скажем, C1, C2, C3 и C4 представляют столбцы данных и имеется N строк данных.Если это так, я мог бы выполнить поиск в хэше, чтобы увидеть, существуют ли некоторые заданные значения для C1, C2, C3, C4.Кто-то предположил мне, что в худшем случае сложность этого пространства будет N ⁴ .Я хотел бы помочь сформулировать четкое объяснение того, почему это не так.

Answer 1

Другой человек думает, что если вы попытаетесь сохранить сетку точек N на N, будет храниться N ⁴ точек.

Но если у вас есть N очков, то вы просто храните хэш. И хеш с N точками данных обычно занимает пространство O (N). (Технически это занимает размер хеш-таблицы плюс пространство для данных, но люди обычно динамически изменяют размер хеш-таблицы на тот же порядок, что и набор данных.)