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

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

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

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

Ответы

Ответ 1

Массивы

  • Установить, проверить элемент по определенному индексу: O (1)
  • Поиск: O (n), если массив несортирован и O (log n), если массив отсортирован и что-то вроде двоичного поиска,
  • Как указано Aivean, в Arrays нет операции 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)

Стек

  • Нажмите: O (1)
  • Поп: O (1)
  • Верх: O (1)
  • Поиск (что-то вроде поиска, как особая операция): O (n) (я полагаю)

Queue/Deque/Circular Queue:

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

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

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

Дерево с красным-черным:

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

Куча /PriorityQueue (мин/макс):

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

HashMap/Hashtable/HashSet:

  • Вставить/Удалить: O (1) амортизировано
  • Re-size/hash: O (n)
  • Содержит: O (1)