Методы Программирования


Структуры данных,
анализ 1 задания








Бобров К. Н.
425 группа





Содержание

Как порядок входных данных влияет на скорость вставки в BST	2
Почему хеш-таблица почти не чувствительна к порядку	4
Почему связный список всегда медленен при поиске	6
Как удаление работает в каждой структуре	7
Вывод	9




Как порядок входных данных влияет на скорость вставки в BST

При вставке отсортированных данных в BST (красный график) производительность падает в разы по сравнению со вставкой случайных данных. Это связано с тем, что отсортированная последовательность приводит к вырождению дерева в связанный список, тогда как случайный порядок вставки помогает сохранять дерево относительно сбалансированным.
При вставке элементов в отсортированном порядке (по возрастанию или убыванию):
?Каждый новый элемент всегда больше (или меньше) всех уже добавленных.
?В результате алгоритм каждый раз движется по одному и тому же направлению — только в правое или только в левое поддерево.
?Из-за этого дерево вырождается: каждый узел имеет не более одного потомка, структура напоминает линейный список.
?Высота такого дерева становится пропорциональной O(n).
?Каждая операция вставки требует в среднем O(n) сравнений, так как нужно проходить всю длину текущей цепочки от корня до самого глубокого листа.
?В итоге суммарная сложность вставки всех n элементов вырастает до O(n^2).


При случайной вставке:
?Элементы распределяются по дереву гораздо равномернее.
?Высока вероятность того, что дерево останется сбалансированным.
?Средняя высота дерева сохраняется на уровне O(logn).
?Каждая операция вставки в среднем требует O(logn) сравнений.
?Общая сложность вставки всех n элементов составляет  O(nlogn).
Вывод: разница в скорости объясняется различием в высоте дерева. В вырожденном случае высота равна O(n), и каждая вставка выполняется в ?n/logn раз медленнее по числу шагов, чем в сбалансированном случае с высотой O(logn).





Почему хеш-таблица почти не чувствительна к порядку


Хештаблица (жёлтый график) демонстрирует почти полную независимость от порядка вставки элементов. Это объясняется тем, что положение каждого элемента в структуре определяется исключительно значением его хешфункции, а не тем, в какой последовательности происходило добавление данных.

Основные причины нечувствительности к порядку вставки:
?Хеширование. Для каждого ключа вычисляется хешкод, который преобразуется в индекс ячейки. Один и тот же ключ всегда даёт один и тот же индекс независимо от того, когда и в каком порядке он был добавлен.
?Независимость операций. Вставка, поиск и удаление выполняются в среднем за O(1)O(1), поскольку алгоритм сразу вычисляет нужную позицию, не обходя структуру и не учитывая историю добавлений.
?Разрешение коллизий. Даже если порядок вставки влияет на расположение элементов внутри цепочки (метод цепочек) или на последовательность проб (открытая адресация), это касается лишь небольших групп элементов с одинаковыми хешами. Общая производительность остаётся стабильной.
?Рехеширование. При увеличении размера таблицы все элементы перераспределяются заново. Новый порядок определяется актуальной хеш-функцией и размером таблицы, а не исходной последовательностью вставки.
Итог: Время выполнения операций зависит от качества хеш-функции, коэффициента заполнения таблицы и метода разрешения коллизий, но не зависит от порядка добавления элементов.





Почему связный список всегда медленен при поиске

Связный список показывает низкую скорость поиска из-за необходимости последовательного обхода: чтобы найти элемент, требуется пройти по указателям от головы до нужного узла.
Почему это происходит:
?Отсутствие произвольного доступа. В отличие от массива, где доступ по индексу занимает O(1), в связном списке элементы приходится перебирать последовательно, что даёт сложность поиска O(n).
?Низкая локальность данных. Узлы списка разбросаны по памяти случайным образом. Это вызывает частые промахи кэша: процессор не может подгрузить блок соседних данных, и каждый переход по указателю оборачивается новым обращением к оперативной памяти.
?Дополнительная память на указатели. Каждый узел хранит не только полезные данные, но и указатель на следующий элемент. Это увеличивает объём памяти и ухудшает эффективность кэша — на те же данные приходится загружать больше информации.
?Затраты на разыменование указателей. На каждом шаге поиска процессору нужно:
oпрочитать текущий узел,
oизвлечь из него указатель на следующий,
oперейти по этому адресу.
Эти операции замедляют работу по сравнению с простым сдвигом индекса в массиве.
Итог: хотя алгоритмическая сложность обхода составляет O(n) как для массива (при линейном поиске), так и для связного списка, на практике список работает ощутимо медленнее из-за особенностей организации памяти и работы кэша.




Как удаление работает в каждой структуре

1. Связный список
Односвязный список: чтобы удалить узел, необходимо сначала найти предыдущий элемент и перенаправить его указатель next на узел, следующий за удаляемым. Исключение — удаление первого элемента: достаточно сдвинуть указатель head на второй узел.
Двусвязный список: удаление проще, поскольку у каждого узла есть указатели и на следующий (next), и на предыдущий (prev). При удалении обновляются ссылки обоих соседей: prev->next = next, next->prev = prev.
Сложность: в общем случае O(n) из-за необходимости поиска элемента; удаление головы или хвоста (при наличии прямой ссылки на хвост) выполняется за O(1).
2. Хештаблица
Сначала через хеш-функцию h(key) вычисляется индекс ячейки. Дальнейшие действия зависят от метода разрешения коллизий:
?Раздельная цепочка: элемент удаляется из связного списка (или другой структуры), находящегося по вычисленному индексу.
?Открытая адресация: ячейка помечается специальным маркером «удалён», а не просто как пустая — это важно для корректности последующих операций поиска.
Сложность: в среднем O(1), в худшем случае O(n) (при большом количестве коллизий).
3. Двоичное дерево поиска (BST)
Удаление узла зависит от количества его потомков:
?Нет детей (лист): узел просто удаляется, ссылка родителя обнуляется.
?Один ребёнок: удаляемый узел заменяется его единственным потомком — родитель «перепрыгивает» через удаляемый узел.
?Два ребёнка:
1.Находится преемник (самый левый (наименьший) узел в правом поддереве) или предшественник (самый правый (наибольший) узел в левом поддереве).
2.Значение преемника/предшественника копируется в удаляемый узел.
3.Преемник/предшественник рекурсивно удаляется — он гарантированно имеет не более одного ребёнка.
Сложность: O(h), где h — высота дерева. В сбалансированном дереве h=O(logn), в несбалансированном — до O(n).

Вывод 
1. Частые вставки
Связный список — отличный выбор для частых вставок (особенно в середину), если не требуется быстрый доступ по индексу. Вставка в начало или конец выполняется за O(1), в середину — за O(n) (но без сдвига элементов, как в массиве).
Хештаблица — хорошо подходит для вставок по ключу, обеспечивая в среднем O(1).
2. Частый поиск
Хештаблица — лучший вариант для быстрого поиска по ключу. Среднее время — O(1), в худшем случае — O(n) (при сильных коллизиях).
Сбалансированное двоичное дерево поиска — предпочтительнее, если нужен поиск с гарантированной сложностью O(logn) даже в худшем случае.
3. Необходимость получать данные в отсортированном порядке
Массив / список — эффективен, если данные уже отсортированы или сортировка происходит редко, а последовательное чтение — часто. Доступ по индексу — O(1), но вставка и удаление в середину требуют O(n).
Отсортированный массив — удобен для поиска (бинарный поиск даёт (O(logn)), однако вставки и удаления обходятся в O(n).
Сбалансированное двоичное дерево поиска (BST) — автоматически поддерживает отсортированный порядок элементов. Все основные операции выполняются за O(logn). Идеальный вариант, когда данные часто изменяются и при этом требуется обход элементов в отсортированном порядке.