Сиаод мирэа 2 семестр. Отчёт_2. Отчет по практической работе 2 Оценка сложности и определение эффективности алгоритма по дисциплине Структуры и алгоритмы обработки данных
![]()
|
![]() МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА
ОТЧЕТ ПО ПРАКТИЧЕСКОЙ РАБОТЕ №2 Оценка сложности и определение эффективности алгоритма по дисциплине «Структуры и алгоритмы обработки данных»
Москва 2023 Содержание Цель работыПриобретение практических навыков, связанных с: определением сложности алгоритмов эмпирическим способом; реализацией алгоритмов сортировки; нахождением эффективного алгоритма решения задачи из нескольких определением емкостной и временной сложностей алгоритма и их зависимости от объема входных данных. Ход работыЗадание 1Формулировка заданияОценить эффективность простого алгоритма сортировки на массиве, заполненном случайными числами (в среднем случае). Используемый алгоритм – Selection Sort. Описание математической моделиИдет проход по массиву с помощью цикла для i. В min записывается значение текущего индекса. С помощью внутреннего цикла происходит поиск минимума и перезапись min. После выполнения внутреннего цикла при неравенстве текущего индекса и min происходит перестановка элементов. Блок-схема алгоритма![]() ![]() Рисунок 1 – блок-схема алгоритма сортировки Код программы![]() ![]() ![]() ![]() ![]() ![]() Рисунок 2 – Алгоритм сортировки Рисунок 3 – Функция вывода массива Рисунок 4 – Функция заполнения массива случайными числами ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Рисунок 8 – Функция main Рисунок 6 – Функция заполнения массива числами по убыванию Рисунок 5 – Функция ручного заполнения массива Рисунок 7 – Функция заполнения массива числами по возрастанию Тестирование![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Рисунок 10 – Тестирование при n = 100. Средний случай Рисунок 9 – Тестирование и отладка при n = 10. Рисунок 11 – Тестирование при n = 1000. Средний случай Рисунок 12 – Тестирование при n = 10 000. Средний случай ![]() ![]() Рисунок 13 – Тестирование при n = 100 000. Средний случай ![]() ![]() Рисунок 14 – Тестирование при n = 1 000 000. Средний случай Обработка результатовТаблица 1 – Selection Sort, средний случай
Оценка емкостной сложностиИспользуется 1 вспомогательная переменная, необходимая для перестановок. Емкостная сложность: ![]() Графики зависимости сложности от nГ ![]() Г ![]() |
Номер оператора | Оператор | Кол-во выполнений оператора в строке |
1 | SelectionSort(int* a, int n) { | |
2 | int tmp, i, j, min; | 4 |
3 | for (i = 1; i <= n-1; i++) do | n |
4 | min = i | n-1 |
5 | for (j=i+1; j<=n; j++) do | ![]() |
6 | if (a[j] < a[min]) then | ![]() |
7 | min = j | ![]() |
8 | endif | |
9 | od | |
10 | if (i != min) then | n-1 |
11 | tmp = a[min] | n/2 |
12 | a[min] = a[i] | n/2 |
13 | a[i] = tmp | n/2 |
14 | endif | |
15 | od | |
16 | } | |
![](1094210_html_fc0ea0c83aeaa3da.gif)
![](1094210_html_d8c5b0efa0c03ccc.gif)
Общая вычислительная сложность алгоритма:
В лучшем случае (массив отсортирован в возрастающем порядке):
![](1094210_html_2708fe086187301b.gif)
В худшем случае (массив отсортирован в убывающем порядке):
![](1094210_html_930f441a12ae210.gif)
Т
естирование
![](1094210_html_a5ae2ea52526c6e4.png)
![](1094210_html_b4d3d005149e92c9.gif)
![](1094210_html_ee70d8825c4146e5.gif)
![](1094210_html_676b99efd7efc3b1.gif)
![](1094210_html_f3d280b42a61fc0d.gif)
![](1094210_html_b4d3d005149e92c9.gif)
![](1094210_html_628b9ce01a318b17.gif)
![](1094210_html_c57338c19360ae8f.gif)
Рисунок 16 – Тестирование при n = 100.
Худший случай
Рисунок 24 – Тестирование при n = 1 000 000.
Худший случай
Рисунок 22 – Тестирование при n = 100 000.
Худший случай
Рисунок 18 – Тестирование при n = 1000.
Худший случай
Рисунок 20 – Тестирование при n = 10 000.
Худший случай
Рисунок 19 – Тестирование при n = 10 000.
Лучший случай
Рисунок 21 – Тестирование при n = 100 000.
Лучший случай
![](1094210_html_89efccf1179db40.gif)
![](1094210_html_628b9ce01a318b17.gif)
![](1094210_html_c07f4e2d6992ee65.gif)
![](1094210_html_83f5fd0ed33dbbdc.png)
![](1094210_html_2642962bd515b1e1.png)
![](1094210_html_5a2ef71724a9ea2f.png)
![](1094210_html_f1497302c4a714b8.png)
![](1094210_html_81f89f19dfffc6db.png)
![](1094210_html_ec194540e72433de.png)
![](1094210_html_f5810457efe9b66a.png)
![](1094210_html_256ed331594e08da.png)
Рисунок 15 – Тестирование при n = 100.
Лучший случай
Рисунок 17 – Тестирование при n = 1000.
Лучший случай
Рисунок 23 – Тестирование при n = 1 000 000.
Лучший случай
Обработка результатов
Лучший случай:
![](1094210_html_312c4dc2f8b81d67.gif)
![](1094210_html_3173c7cadf52675a.gif)
![](1094210_html_e8ef6f1e5ac3692e.gif)
![](1094210_html_24eafa90c014de21.gif)
![](1094210_html_646af36b0b73e26f.gif)
Таблица 2 – Selection Sort, лучший случай
n | T(n), мс | Тп(n) = Cф + Mф | Тт(n) = С + М |
100 | 0,046 | 10 301 | 10 301 |
1000 | 2,257 | 1 003 001 | 1 003 001 |
10 000 | 201,208 | 100 030 001 | 100 030 001 |
100 000 | 20 159,500 | 10 000 300 001 | 10 000 300 001 |
1 000 000 | 2 022 320,000 | 1 000 003 000 001 | 1 000 003 000 001 |
Худший случай:
![](1094210_html_50e2a11b3a9c7dc6.gif)
![](1094210_html_c571795697402dc.gif)
![](1094210_html_f3868a98b4631d3b.gif)
![](1094210_html_cf60bb2ecc0216b8.gif)
![](1094210_html_c11e2743d50bc273.gif)
Таблица 3 – Selection Sort, худший случай
n | T(n), мс | Тп(n)=Cф+Mф | Тт(n)=С+М |
100 | 0,014 | 12 951 | 12 951 |
1000 | 1,146 | 1 254 501 | 1 254 501 |
10 000 | 115,184 | 125 045 001 | 125 045 001 |
100 000 | 12 382,100 | 12 500 450 001 | 12 500 450 001 |
1 000 000 | 1 536 200,000 | 1 250 004 500 001 | 1 250 004 500 001 |
График зависимости сложности от n
Г
![](1094210_html_15bf952779560935.gif)
Вывод по заданию 2
Полученные данные подтверждают, что сложность алгоритма имеет квадратичный характер вне зависимости от исходного состояния массива. Результаты теоретического расчета и практического выполнения совпали. В худшем случае сложность определяется формулой
![](1094210_html_930f441a12ae210.gif)
![](1094210_html_2708fe086187301b.gif)
Задание 3
Формулировка задания
Сравнить эффективность двух алгоритмов простых сортировок. Второй используемый алгоритм – Exchange Sort.
Описание математической модели
Осуществляется проход по массиву от 1 элемента до n-ного, сравнивая текущий элемент со всеми последующими. Если какой-то из последующих элементов меньше i-того, то меняем их местами.
Блок-схема алгоритма
![](1094210_html_32873c27a31ba647.gif)
![](1094210_html_321686b2dbb2a86f.png)
Рисунок 25 – блок-схема алгоритма сортировки
Реализация алгоритма
![](1094210_html_8eea81e5b8446d69.png)
![](1094210_html_463140dff4596994.gif)
Рисунок 26 – Алгоритм сортировки
Тестирование
![](1094210_html_f28255adb5aa04d7.png)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_95def0387f9732fe.png)
Рисунок 28 – Тестирование при n = 100. Лучший случай
Рисунок 27 – Тестирование и отладка при n = 10.
![](1094210_html_78881368c3b99fd2.png)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_ac69f877e2ccdd7d.gif)
![](1094210_html_fac42fd7d1ee7848.png)
![](1094210_html_46ea48efb9b3e1b8.png)
![](1094210_html_f2a2f2fe4ec2b2d.png)
![](1094210_html_f2319bb157fc8e23.png)
Рисунок 33 – Тестирование при n = 10 000. Худший случай
Рисунок 30 – Тестирование при n = 1000. Лучший случай
Рисунок 29 – Тестирование при n = 100. Худший случай
Рисунок 31 – Тестирование при n = 1000. Худший случай
Рисунок 32 – Тестирование при n = 10 000. Лучший случай
![](1094210_html_3a47c2e7a451d7f7.png)
![](1094210_html_ac69f877e2ccdd7d.gif)
Рисунок 34 – Тестирование при n = 100 000. Лучший случай
![](1094210_html_6f1cb9343ad81ce2.png)
![](1094210_html_ac69f877e2ccdd7d.gif)
Рисунок 35 – Тестирование при n = 100 000. Худший случай
![](1094210_html_edd6cbc652d15a5f.png)
![](1094210_html_b823bb0d9ce56ec4.gif)
![](1094210_html_b823bb0d9ce56ec4.gif)
![](1094210_html_c35dbf0049ee96bd.png)
Рисунок 37 – Тестирование при n = 1 000 000. Худший случай
Рисунок 36 – Тестирование при n = 1 000 000. Лучший случай
Обработка результатов
Таблица 4 – Exchange Sort, лучший случай
n | T(n), мс | Тп(n) = Cф + Mф |
100 | 0,036 | 10 100 |
1000 | 2,135 | 1 001 000 |
10 000 | 193,155 | 100 010 000 |
100 000 | 15 030,900 | 10 000 100 000 |
1 000 000 | 1 188 420,000 | 1 000 001 000 000 |
Таблица 5 – Exchange Sort, худший случай
n | T(n), мс | Тп(n) = Cф + Mф |
100 | 0,029 | 24 950 |
1000 | 3,287 | 2 499 500 |
10 000 | 297,304 | 249 995 000 |
100 000 | 20 466,900 | 24 999 950 000 |
1 000 000 | 1 740 970,000 | 2 499 999 500 000 |
Оценка емкостной сложности
Используется 1 вспомогательная переменная, необходимая для перестановок. Емкостная сложность:
![](1094210_html_988f4c163900c8ef.gif)
Графики зависимости сложности от n
Г
![](1094210_html_cc850f58e4801707.gif)
Г
![](1094210_html_7560026cde318655.gif)
Вывод по заданию 3
Полученные данные подтверждают, что оба алгоритма обладают квадратичной вычислительной сложностью, но на основе теоретического расчета можно установить, что функция роста второго алгоритма растет быстрее. Основываясь на графиках и таблицах, можно утверждать, что время выполнения зависит и от исходного состояния массива. Наибольшая разница заметна при худшем случае, в то время как сложности в лучшем и среднем случаях практически совпадают. Емкостная сложность у обоих алгоритмов – константная.
Вывод
В ходе работы приобретены и отработаны практические навыки по:
определению сложности алгоритмов сортировки на теоретическом и практическом уровнях;
определению емкостной сложности алгоритмов сортировки;
реализацией алгоритмов сортировки;
определению зависимости (квадратичной/линейной) сложности алгоритма сортировки от объема входных данных;
нахождению оптимального алгоритма сортировки с помощью данных, полученных в ходе теоретического расчета и практического выполнения.