Почему считается, что хэш-карта имеет сложность O (1)?

Question

Предположим, у нас есть следующий класс хэш-карт в Javascript:

class myHash {
    constructor() {
        this.list = [];
    }
    hash(input) {
        var checksum = 0;
        for (var i = 0; i < input.length; i++) {
            checksum += input.charCodeAt(i);
        }
        return checksum;
    }
    get(input) {
        return (this.list[this.hash(input)]);
    }
    set(input, value) {
        this.list[this.hash(input)] = value;
    }
}

Функция hash имеет цикл со сложностью O(n), который вызывается во время получения и установки.Разве это не делает сложность хэш-карты O(n)?

Answer 1

Да, размер строки (k) имеет значение.(точнее, сложность хеш-функции)

---

Предположим:

• Получить индекс массива использования элемента занимает f(n) время
• Хеш-функция принимает g(k) время

тогда сложность составляет O( f(n)+g(k) ).

Мы знаем , что g(k) равно O(k), и если мы предполагаем f(n) равно O(1), сложность становится O(k)

Более того, если мы предположим размер строки k будет не больше, чем константа c, сложность становится O(c), которую можно переписать как O(1).

---

Таким образом, на самом деле, учитывая вашу реализацию, O(1) является правильной границей, только если

• Получить индекс использования массива элементов занимает O(1)
• Строка не длиннее константы c

---

Примечания

• Некоторая хеш-функция может сама по себе быть O(1), например, просто взять первый символ или длину.
• Должна быть проверена необходимость получения индекса массива get элемента O(1), например, вРазреженный массив javascript может занять больше времени для доступа.

Answer 2

Когда вы выполняете анализ Big-O, вам нужно очень четко понимать, что это за переменные. Часто n оставляют неопределенным или подразумеваемым, но важно знать, что именно.

• Давайте определим n как количество элементов в хэш-карте.

Когда n является единственной рассматриваемой переменной, тогда все методы являются O (1). Ни один из них не зацикливается на this.list, и поэтому все они работают в постоянное время относительно количества элементов в хэш-карте .

Но вы возражаете: в hash() есть петля. Как это может быть O (1). Ну, что это зацикливается? Зацикливается ли оно на других объектах на карте? Нет. Это зацикливание на input - но input.length - не та переменная, которую мы рассматриваем.

Когда люди анализируют производительность хеш-карты, они обычно игнорируют длину передаваемых строк. Если мы сделаем это, тогда относительно n производительности хеш-карты составит O (1) * +1032 *. * * 1 033 Если вам важны длины строк, вам нужно добавить еще одну переменную в анализ.

• Давайте определим n как количество элементов в хэш-карте.
• Давайте определим k как длину читаемой / записываемой строки.

Хеш-функция равна O ( k ), поскольку она циклически перебирает входную строку за линейное время. Следовательно, get() и set() также O ( k ).

Почему нас не волнует k нормально? Почему люди говорят только о n ? Это потому, что k является фактором при анализе производительности хеш-функции, но когда мы анализируем, насколько хорошо работает хеш-карта, нам не особо важно, насколько быстро работает хеш-функция. Мы хотим знать, насколько хорошо работает сама хэш-карта, и на k не влияет ни один из ее кодов. Только hash() есть, а hash() не является частью хэш-карты, это всего лишь вход в нее.