Big O - Создание Hashtable со значениями - сложность времени

Question

Я и мои однокурсники давно обсуждали, что для этого важно: создание хеш-таблицы со значениями путем итеративной вставки (число элементов известно в начале) в среднем и худшем случаях.

Средняя сложность вставки 1 элемента - O (1), поэтому вставка n элементов в пустую хеш-таблицу должна быть O (n).

В худшем случае вставка 1 элемента - O (n). Итак, вставляет ли n элементов в пустую хеш-таблицу O (n ^ 2) или O (n) и почему?

Answer 1

Наихудший случай случается, когда каждая вставка приводит к столкновению. Стоимость столкновения зависит от реализации таблицы ha sh. Самой простой реализацией обычно является связанный список всех элементов, принадлежащих одной ячейке ha sh. Таким образом, вставка n элементов будет стоить 1+2+3+..+n единиц времени. Это сумма арифметических рядов c и она равна n (n + 1) / 2 = O (n ² ). Этот результат можно улучшить, используя более сложные структуры данных для обработки коллизий. Например, для дерева AVL стоимость вставки составляет O (logn), т. Е. Для n элементов это будет O (log1 + log2 + ... + logn) = O (log (n!)), Что значительно лучше, чем O (п ² ).