Алгоритмическая сложность

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

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

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

КИБЭВС

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

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

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

Студент гр. 721-2

_______ Д. М. Мусин

_______

Принял:

преподаватель КИБЭВС

_______ Н. С. Репьюк

 _______

Томск 2022

Содержание 

Введение        3

2        Ход работы        4

2.1 Сортировка расческой        4

2.2 Быстрая сортировка        8

2.3 Сортировка вставками        12

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

Приложение А        18

Приложение Б        19

Приложение В        20

Введение

Целью работы является вычисление алгоритмической сложности ранее реализованных сортировок в рамках Практической работы №2.

Для выполнения Практической работы №2, были предоставлены 4 задания.

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

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

1. Вывести на графики данные по числу операций, по времени сортировки в зависимости от размера массива (зависимость числа операций от размера массива, зависимость времени выполнения алгоритма от размера массива). Для каждой сортировки сделайте разные графики.
2. На каждый график сортировки с числом операций выведете график эталонных функций: y=n, y=n*log(n), y=n^2, y=n^3 (зависимость числа операций от размера массива). ТАБЛИЦЫ с замерами числа операций и времени также представьте в отчете. 
3. Сделать выводы об алгоритмической сложности каждого алгоритма оценив форму графиков зависимости из пункта 2. Написать текст вывода в отчете. 
4. Для каждой рассмотренной сортировки сгенерировать лучший и худший варианты (массивы длиной 100 элементов) и получить значения для них по числу операций и перестановок, и времени сортировки. Проделать по 5 экспериментов, а каждую сортировку и усреднить значения. Лучший вариант — это уже отсортированный массив. Худший вариант — это отсортированный в обратном направлении массив. Сделать выводы. Результаты представить в таблице.

Для решения данных заданий был использован язык программирования C#

Ход работы

2.1 Сортировка расческой

На рисунке 2.1 представлен график зависимости времени выполнения сортировки от количества элементов.

[pic 1]

Рисунок 2.1 – График зависимости времени от количества элементов массива

На рисунке 2.2 изображена таблица с замерами числа операций, времени и количества элементов в массиве.

[pic 2]

Рисунок 2.2 – Таблица замеров числа операций, времени и количества элементов в массиве

На рисунке 2.3 изображен график эталонной функции y = n для зависимости числа операций от количества элементов в массиве.

[pic 3]
Рисунок 2.3 – Эталонная функция y = n

На рисунке 2.4 изображен график эталонной функции y=n*log(n)

для зависимости числа операций от количества элементов в массиве.

[pic 4]

Рисунок 2.4 - Эталонная функция y=n*log(n)

На рисунке 2.5 изображен график эталонной функции y=n^2.

для зависимости числа операций от количества элементов в массиве.

[pic 5]

Рисунок 2.5 – Эталонная функция y=n^2

На рисунке 2.6 изображен график эталонной функции y=n^3

для зависимости числа операций от количества элементов в массиве.