forked from UNN/2026-rff_mp
35 lines
2.7 KiB
Markdown
35 lines
2.7 KiB
Markdown
ОТЧЁТ ПО ЗАДАНИЮ 1
|
||
|
||
1. Влияние порядка данных на BST
|
||
При случайном порядке данных BST работает быстро (вставка ~0.005 сек).
|
||
При отсортированном порядке дерево вырождается в цепочку, и время вставки
|
||
возрастает примерно в 50–60 раз (~0.31 сек). Сложность деградирует с O(log n) до O(n).
|
||
|
||
2. Почему хеш-таблица нечувствительна к порядку
|
||
Хеш-таблица использует хеш-функцию, которая равномерно распределяет элементы
|
||
по бакетам. Поэтому порядок входных данных почти не влияет на скорость
|
||
вставки, поиска и удаления (в среднем O(1)).
|
||
|
||
3. Почему связный список медленен при поиске
|
||
Для поиска в связном списке нужно последовательно пройти все элементы.
|
||
Поэтому поиск всегда выполняется за O(n), независимо от порядка данных.
|
||
Это делает его самым медленным при операциях поиска и удаления.
|
||
|
||
4. Как работает удаление
|
||
- LinkedList: O(n) — нужно найти элемент и перестроить ссылки.
|
||
- HashTable: O(1) в среднем — удаление внутри нужного бакета.
|
||
- BST: O(log n) в среднем, O(n) в худшем — при двух потомках ищется
|
||
минимальный элемент в правом поддереве.
|
||
|
||
5. Вывод и рекомендации
|
||
|
||
Рекомендуемые структуры в зависимости от задачи:
|
||
|
||
- Частые вставки и поиск → HashTable (лучшая общая производительность)
|
||
- Нужно получать данные в отсортированном порядке → BST (только при случайных данных)
|
||
- Данные приходят отсортированными → HashTable (BST сильно деградирует)
|
||
- Малый объём данных и простота → LinkedList
|
||
|
||
Итог: Для большинства реальных задач лучше всего подходит хеш-таблица.
|
||
BST имеет смысл использовать только при случайном порядке данных и
|
||
необходимости частого получения отсортированного списка. |