Сложность операций для структур данных

data-structures-complexity.md

Сложности основных операций для различных структур данных:

Stack (Стек)

• Добавление (push): O(1)
• Поиск: O(n)
• Удаление (pop): O(1)
• Вставка: O(n)
• Обход: O(n)

Map (Хеш-таблица)

• Добавление: O(1) в среднем, O(n) в худшем случае
• Поиск: O(1) в среднем, O(n) в худшем случае
• Удаление: O(1) в среднем, O(n) в худшем случае
• Вставка: O(1) в среднем, O(n) в худшем случае
• Обход: O(n)

Set (Множество)

• Добавление: O(1) в среднем, O(n) в худшем случае
• Поиск: O(1) в среднем, O(n) в худшем случае
• Удаление: O(1) в среднем, O(n) в худшем случае
• Вставка: O(1) в среднем, O(n) в худшем случае
• Обход: O(n)

List (Динамический массив)

• Добавление (в конец): O(1) в среднем
• Поиск: O(n)
• Удаление: O(n)
• Вставка: O(n)
• Обход: O(n)

Array (Статический массив)

• Добавление (в конец): O(1)
• Поиск: O(n)
• Удаление: O(n)
• Вставка: O(n)
• Обход: O(n)

Queue (Очередь)

• Добавление (enqueue): O(1)
• Поиск: O(n)
• Удаление (dequeue): O(1)
• Вставка: O(n)
• Обход: O(n)

Linked List (Связный список)

• Добавление (в начало/конец): O(1)
• Поиск: O(n)
• Удаление (из начала/конца): O(1)
• Вставка (в произвольное место): O(n)
• Обход: O(n)

Бинарное дерево поиска (BST)

• Добавление: O(h) в среднем, O(n) в худшем случае
• Поиск: O(h) в среднем, O(n) в худшем случае
• Удаление: O(h) в среднем, O(n) в худшем случае
• Вставка: O(h) в среднем, O(n) в худшем случае
• Обход: O(n)

где h - высота дерева, n - количество узлов.

AVL-дерево

• Добавление: O(log n)
• Поиск: O(log n)
• Удаление: O(log n)
• Вставка: O(log n)
• Обход: O(n)

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

• Добавление: O(log n)
• Поиск: O(log n)
• Удаление: O(log n)
• Вставка: O(log n)
• Обход: O(n)

B-дерево

• Добавление: O(log n)
• Поиск: O(log n)
• Удаление: O(log n)
• Вставка: O(log n)
• Обход: O(n)

2-3 дерево

• Добавление: O(log n)
• Поиск: O(log n)
• Удаление: O(log n)
• Вставка: O(log n)
• Обход: O(n)

Важно отметить, что сбалансированные деревья (AVL, красно-черные, B-деревья, 2-3 деревья) обеспечивают логарифмическую сложность для основных операций даже в худшем случае, в то время как обычное бинарное дерево поиска может деградировать до линейной сложности.

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

B-деревья и их варианты особенно эффективны для работы с большими объемами данных и часто используются в базах данных и файловых системах.

Обход дерева всегда имеет линейную сложность O(n), так как требует посещения каждого узла один раз.

Примечание: Сложность операций может варьироваться в зависимости от конкретной реализации структуры данных и особенностей использования.