sd_2

1

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

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

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

Кафедра безопасности информационных систем(БИС)

АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ

Отчет по практической работе №2

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

Выполнил Студент гр. 730-2

Подойницын К.В.

16.09.2021

Принял Инженер научно-технического отдела ЦСП

Уразаев Д.Р.

16.09.2021

Томск 2021

2

Задание

Сгенерировать массивы заданной длины.

Последовательно задайте длину массивов 1, 2, 3, 4, 5, 10, 15, 20,25, 30, 40,50, 75, 100,150,200,250, 300, 400, 500, 600, 800, 1000.

Отсортировать все массивы исследуемыми алгоритмами сортировки и подсчитать количество операций, выполненных для их сортировки (количество сравнений + количество перестановок) и

время затраченное на сортировку массивов.

1.Вывести на графики данные по числу операций, по времени сортировки в зависимости от размера массива (зависимость числа операций от размера массива, зависимость времени выполнения алгоритма от размера массива). Для каждой сортировки сделайте разные графики.

2.На каждый график сортировки с числом операций выведете график эталонных функций: : y=n, y=n*log(n), y=n^2, y=n^3 (зависимость числа операций от размера массива)

3.Сделать выводы об алгоритмической

сложности каждого

алгоритма оценив форму графиков зависимости из пункта 2

4. Для каждой рассмотренной сортировки сгенерировать лучший и худший варианты (массивы длиной 100 элементов) и

получить значения для них по числу операций и перестановок и времени сортировки. Проделать по 5 экспериментов а каждую сортировку и усреднить значения. Лучший вариант - это уже отсортированный массив. Худший вариант - это отсортированный в

3

обратном направлении массив. Сделать выводы. Результаты представить в таблице.

5.Сформировать отчет с разделами

4

5

1.Введение

Цель работы состоит в подсчете времени выполнения и количества операций при осуществлении сортировки расчёской, быстрой сортировки и сортировки вставками. А также в построении графиков зависимости и оценке алгоритмической сложности каждой сортировки.

6

2.Основная часть

2.1 Сортировка Шелла

Для оценки алгоритмической сложности сортировки построим

графики зависимости количества операций от длины массива (рисунок

2.2) и график зависимости времени от длины массива (рисунок 2.1).

Рисунок 2.1 – Сортировка Шелла. Зависимость времени выполненияалгоритма от размера массива

7

Рисунок 2.2 – Сортировка Шелла. Зависимость числа операций от размерамассива

Как видно из рисунка 2.2 в худшем случае алгоритмическая сложность будет равной O(n^2), а в лучшем O(n*log(n)). Это соответствует теоретическим данным.

Листинг программы указан в Приложении A

2.2 Сортировка расчёской

Рисунок 2.3 – Сортировка расческой. Зависимость времени выполненияалгоритма от размера массива

8

Рисунок 2.4 – Сортировка расческой. Зависимость числа операций отразмера массива

Как видно из рисунка 2.4 алгоритмическая сложность находится

между O(n^2) и O(n*log(n)). Это соответствует теоретическим

данным.

Листинг программы указан в Приложении B

2.3 Быстрая сортировка

9

Рисунок 2.5 – Быстрая сортировка. Зависимость числа операций от размера массива

Рисунок 2.6 – Быстрая сортировка. Зависимость числа операций от размера массива

Как видно из рисунка 2.6 алгоритмическая сложность находится

между O(n^2) и x *log(x). Это соответствует теоретическим

данным.

Листинг программы указан в Приложении C

2.4 Анализ таблицы

Таблица 2.1

Анализируя данную таблицу, можно сделать вывод, что быстрая

сортировка является самой лучшей

10

3.Заключение

Входе выполнения лабораторной работы были реализованы сортировки и проанализированы их алгоритмические сложности, так же найдены худшие и лучшие варианты для сортировок. Цели работы были достигнуты. Результаты по данным сортировкам совпали с теоретическими.