chizhikovasm/2026-rff_mp
1
0
Fork 0
forked from UNN/2026-rff_mp
Code Pull Requests Activity
task1
2026-rff_mp/chizhikovasM/docs/report_1-st-exersize.md

3.8 KiB
Raw Permalink Blame History

Отчет по лабораторной работе "Структуры данных"

1)Среднее время выполнения (в секундах)

Структура Режим Вставка (1000) Поиск (110) Удаление (50)
LinkedList случайный 0.574278 0.027799 0.385323
LinkedList отсортированный 0.389446 — —
HashTable случайный 0.036228 0.001376 0.027784
HashTable отсортированный 0.041256 — —
BST случайный 0.007626 0.000781 0.008064
BST отсортированный 0.463135 — —

2)Графическое представление график в коде

Диаграмма сравнения времени выполнения операций для трёх структур данных

3)Анализ результатов

  1. Влияние порядка данных на BST
Параметр Случайный порядок Отсортированный порядок Изменение
Время вставки 0.0076 сек 0.4631 сек намного медленнее

Каждый новый элемент добавляется в самый правый узел, и дерево теряет свою сбалансированность.

  1. Устойчивость хеш-таблицы к порядку данных
Параметр Случайный порядок Отсортированный порядок
Время вставки 0.0362 сек 0.0413 сек

Хеш-функция sum(ord(ch)) % size равномерно распределяет записи. Даже если имена приходят отсортированными, они попадают в разные корзины случайным образом.

  1. Медлительность связного списка при поиске
Операция LinkedList HashTable BST (случайный)
Поиск (110 записей) 0.0278 сек 0.0014 сек 0.0008 сек
  • Хеш-таблица быстрее связного списка в 20 раз
  • BST быстрее связного списка в 35 раз Поиск в связном списке требует линейного прохода от головы до конца:

· В худшем случае нужно проверить все 1000 элементов · Нельзя "перепрыгнуть" к нужному элементу

  1. Сравнение операций удаления
Структура Время удаления (50 записей)
LinkedList 0.3853 сек
HashTable 0.0278 сек
BST (случайный) 0.0081 сек

BST и хеш-таблица значительно превосходят связный список по скорости удаления 5)итог

  1. Для частого поиска → Хеш-таблица (O(1))
  2. Для частых вставок/удалений на случайных данных → BST (O(log n))
  3. Для получения данных в отсортированном порядке → BST (in-order обход)
  4. Для маленьких объёмов данных → любой, но LinkedList проще
  5. Для отсортированных входных данных → НЕ использовать BST (деградация до O(n))