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

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

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

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

1 71
javascript data-structures time-complexity

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) если где-нибудь еще, так как мы должны достичь этой позиции, перемещая linkedlist линейно.
  • удаление:O (1), если сделано в голове,O (n) если где-нибудь еще, так как мы должны достичь этой позиции, перемещая linkedlist линейно.
  • Поиск: O (n)

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

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

стопка:

  • Push:O (1)
  • поп:O (1)
  • Top:O (1)
  • Поиск (что-то вроде поиска, как спецоперация): O (n) (Я так думаю)

Queue / Deque / Circular Очередь:

  • вставить: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)
  • Поиск, Удалить (если вообще предоставляется): O (n), нам придется сканировать все элементы, поскольку они не упорядочены, как BST

HashMap/Hashtable/HashSet:

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