JDC StdLog👁‍ (@jeusdevstd) — Telegram Channel

Post #496 25 May 25, 2026, 10:46 UTC

🐳 3

Post #495 43 May 25, 2026, 10:26 UTC

Асимптотическая сложность (Нотация BigO)

BigO (O) показывает, как растет время работы или объем памяти алгоритма при увеличении размера входных данных (n). Она игнорирует константы и берет самый быстрорастущий член функции.

O(1) - Константная: Время выполнения не зависит от размера данных (например, доступ к элементу массива по индексу).
O(log n) - Логарифмическая: Время растет очень медленно. Идеально для больших объемов данных (например, бинарный поиск).
O(n) - Линейная: Время прямо пропорционально размеру данных (например, линейный поиск).
O(n log n) - Квазилинейная: Типично для эффективных алгоритмов сортировки (например, быстрая или пирамидальная сортировки).
O(n^2) - Квадратичная: Часто встречается во вложенных циклах (например, пузырьковая сортировка).

Сравнение производительности коллекций

Массивы / списки (Array / ArrayList):
- доступ по индексу: O(1)
- поиск значения: O(n)
- вставка/удаление (в конец): O(1) амортизированное
- вставка/удаление (в начало/середину): O(n)

Связные списки (LinkedList):
- доступ по индексу: O(n)
- вставка/удаление (известный узел): O(1)

Хеш-таблицы (HashSet / HashMap):
- поиск, вставка, удаление: O(1) в среднем случае. В худшем случае (коллизии) - O(n)

Дерево-подобные коллекции (TreeSet / TreeMap):
- поиск, вставка, удаление: O(log n)
- элементы всегда хранятся в отсортированном порядке

Деревья

Дерево - это иерархическая структура данных, состоящая из узлов, связанных между собой ребрами

Главные компоненты:
- корень (Root): верхний узел, не имеющий предков.
- потомок / Родитель (Child / Parent): узлы на разных уровнях иерархии.
- лист (Leaf): узел без потомков

Бинарное дерево: Дерево, у которого каждый узел имеет не более двух потомков.

Бинарное дерево поиска (BST): Упорядоченное дерево. Для каждого узла все элементы в левом поддереве меньше его, а в правом - больше. Это обеспечивает поиск за O(log n).

Самобалансирующиеся деревья (например, AVL-деревья, Красно-черные деревья): Деревья, которые автоматически перестраиваются при добавлении/удалении элементов, чтобы их высота не превышала O(log n), гарантируя высокую скорость работы.