Каковы временные сложности различных структур данных?

Question

Я пытаюсь перечислить временные сложности операций общих структур данных, таких как массивы, дерево двоичного поиска, куча, связанный список и т. Д., И особенно я имею в виду Java.Они очень распространены, но я думаю, что некоторые из нас не уверены на 100% в точном ответе.Любая помощь, особенно ссылки, очень ценится.

Например, для односвязного списка: изменение внутреннего элемента - O (1).Как ты можешь это сделать?Вы ДОЛЖНЫ искать элемент перед его изменением.Также для вектора добавление внутреннего элемента дается как O (n).Но почему мы не можем сделать это в амортизированном постоянном времени, используя индекс?Пожалуйста, поправьте меня, если я что-то упустил.

Я публикую свои выводы / предположения в качестве первого ответа.

Answer 1

Массивы

• Установить, проверить элемент по определенному индексу: O (1)
• Поиск : O (n) , если массив не отсортирован и O (log n) , если массив отсортирован и используется что-то похожее на двоичный поиск,
• Как указано Aivean , в массивах нет операции Delete.Мы можем символически удалить элемент, установив для него определенное значение, например, -1, 0 и т. Д. В зависимости от наших требований
• Аналогично, Insert для массивов в основном равно Set, как упоминалось в начале

ArrayList:

• Добавить : Амортизированный O (1)
• Удалить : O (n)
• Содержит : O (n)
• Размер : O (1)

Связанный список:

• Вставка : O (1) ,если сделано в голове, O (n) , если где-либо еще, так как мы должны достичь этой позиции путем линейного перемещения связного списка.
• Удаление : O(1) , если сделано в голове, O (n) , если где-либо еще, поскольку мы должны достичь этой позиции путем линейного перемещения связного списка.
• Поиск : O (n)

Список с двойной связью:

• Вставка : O (1) , если сделано в голове или хвосте, O (n) , если где-либо еще, так как мы должны достичь этой позиции путем линейного перемещения связного списка.
• Удаление : O (1) , если сделано в голове или хвосте, O (n) , если где-либо еще, так как мы должны достичь этой позиции путем линейного перемещения связного списка.
• Поиск : O (n)

Стек:

• Push : O (1)
• Pop : O (1)
• Верх : O (1)
• Поиск (что-то вроде поиска в качестве специальной операции): O (n) (наверное, так)

Очередь / Deque / Круговая очередь:

• Вставить : O (1)
• Удалить: O (1)
• Размер : O (1)

Дерево двоичного поиска:

• Вставка, удаление и поиск : Средний регистр: O (log n) , наихудший случай: O (n)

Красно-черное дерево:

• Вставка, удаление и поиск : Средний регистр: O (log n) , Худший случай: O (log n)

Heap / PriorityQueue (min / max):

• Найти мин. / Найти макс. : O (1)
• Вставить : O (log n)
• Удалить Мин. / Удалить Макс. : O (log n)
• Изв. Мин. / Изв. Макс. : O (log n)
• Lookup, Delete (если вообще предусмотрено): O (n) , нам придется сканироватьвсе элементы, как они не упорядочены, как BST

HashMap / Hashtable / HashSet:

• Вставить / Удалить : O (1) амортизируется
• Изменить размер / хэш : O (n)
• Содержит : O (1)