Асимптотическая сложность (Нотация 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), гарантируя высокую скорость работы.