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

Ответ 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.

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

• Вставка - O (log n)
• Retrieve - O (log n)
• Удалить - O (log n)

Ответ 5

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

• Вставка - O (1)
• Retrieve - O (1)
• Удалить - O (1)

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