Какова временная сложность индексации, вставки и удаления из общих структур данных?

Question

Сводная нотация большого О не доступна для операций с наиболее распространенными структурами данных, включая массивы, связанные списки, хеш-таблицы и т. Д.

Answer 1

Информация по этой теме теперь доступна в Википедии по адресу: Структура поиска данных

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. 
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.

Answer 2

Полагаю, я начну с сложности времени связанного списка:

Индексирование ----> О (п)
Вставка / удаление в конце ----> O (1) или O (n)
Вставка / удаление в середине ---> O (1) с итератором O (n) без

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

Answer 3

Имейте в виду, что если вы не пишете свою собственную структуру данных (например, связанный список в C), это может сильно зависеть от реализации структур данных в выбранном вами языке / структуре. В качестве примера рассмотрим тесты Apple CFArray на Ridiculous Fish . В этом случае тип данных, CFArray из инфраструктуры Apple CoreFoundation, фактически изменяет структуры данных в зависимости от того, сколько объектов фактически находится в массиве, - с линейного времени на постоянное время около 30 000 объектов.

Это на самом деле одна из прекрасных вещей в объектно-ориентированном программировании - вам не нужно знать как это работает, просто , что это работает, и 'как это' работы могут меняться в зависимости от требований.

Answer 4

Ничего более полезного, чем это: Операции с общей структурой данных :

Answer 5

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

• Вставка - O (log n)
• Получить - O (log n)
• Удалить - O (log n)

Answer 6

Амортизированный Big-O для хеш-таблиц:

• Вставка - O (1)
• Получить - O (1)
• Удалить - O (1)

Обратите внимание, что для алгоритма хеширования существует постоянный коэффициент, а амортизация означает, что фактическая измеренная производительность может значительно отличаться.