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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра КСУП

Отчёт по дисциплине «Структуры данных»

ВРЕМЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ ДВУСВЯЗНОГО СПИСКА

Выполнил:

Студент гр. 580-1

 __________ .

17.12.2021

Проверил:

Профессор кафедры ФВС

__________ .

17.12.2021

Томск 2021

Содержание

1 Введение        2

2 Цель работы        2

3 Результаты работы и их анализ        2

3.1 Операция сортировки        2

3.2 Остальные операции        7

4. Заключение        8

1 Введение

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

2 Цель работы

Исследовать зависимость времени выполнения операций двусвязного списка от количества элементов в нём.

3 Результаты работы и их анализ

Выполним измерения с помощью встроенных средств языка, а именно с помощью библиотеки «choro».

3.1 Операция сортировки

Таблица 3.1.1 - Время затраченное на сортировку списка в зависимости от количества элементов в нём

Построим график по таблице (3.1.1), отложим по оси абсцисс количество элементов, а по оси ординат время выполнения операции.

График 3.1.2 - Время затраченное на сортировку списка в зависимости от количества элементов в нём

[pic 1]

Из графика можно сделать вывод, что это параболическая функция , сделаем предположение что она имеет степень двойки, тогда найдём её параметр для каждой отдельной точки по формуле , где  это время выполнения в секундах, а  число элементов в списке из таблицы (3.1.1).[pic 2][pic 3][pic 4][pic 5]

Таблица 3.1.3 - Параметр параболической функции для каждой соответствующей точки из таблицы (3.1.1).