Практическая работа по СИАОДУ №1. Практическая работа №1 сиаод (6). Оценка вычислительной сложности алгоритма
 Скачать 0.85 Mb.
|
|
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «МИРЭА – Российский технологический университет» РТУ МИРЭА Отчет по выполнению практического задания № 1.1 Тема: «Оценка вычислительной сложности алгоритма» Дисциплина: «Структуры и алгоритмы обработки данных» Выполнил студент: Амерханов К.А. Фамилия И.О. Группа: ИКБО-35-22 Номер группы Москва – 2023 2 СОДЕРЖАНИЕ 1 ЦЕЛЬ РАБОТЫ................................................................................................... 3 2 ЗАДАЧА №1 ......................................................................................................... 4 2.1 Формулировка задачи................................................................................... 4 2.2 Математическая модель решения задачи ................................................ 5 2.3 Реализация алгоритма в виде функции .................................................. 10 2.4 Тестирование алгоритма в ситуациях ..................................................... 10 2.5 Оценка ёмкости сложности алгоритма ................................................... 12 2.6 Вывод по заданию № 1 ................................................................................ 12 2.7 Реализация структурированного кода программы с комментариями на основе блок- схемы 12 3 ЗАДАЧА №2 ........................................................................................... 14 3.1 Формулировка задачи................................................................................. 14 3.2 Математическая модель решения задачи .............................................. 14 3.3 Реализация алгоритма ................................................................................ 15 3.4 Тестирование алгоритма ............................................................................ 15 3.5 Выполнение практической оценки сложности ...................................... 16 3.6 Оценить ёмкостную сложность алгоритма ............................................ 16 3.7 Результаты выполнения алгоритма ........................................................ 16 3.8 Вывод ............................................................................................................. 17 3 1 ЦЕЛЬ РАБОТЫ Цель: приобретение практических навыков: • эмпирическому определению вычислительной сложности алгоритмов на теоретическом и практическом уровнях; • выбору эффективного алгоритма решения вычислительной задачи из нескольких. 4 2 ЗАДАЧА №1 2.1 Формулировка задачи Задание 1. Выбрать эффективный алгоритм вычислительной задачи из двух предложенных, используя теоретическую и практическую оценку вычислительной сложности каждого из алгоритмов, а также его ёмкостную сложность. Пусть имеется вычислительная задача: – дан массив х из n элементов целого типа; удалить из этого массива все значения равные заданному (ключевому) key. 5 2.2 Математическая модель решения задачи a) Составление блок-схемы алгоритмов программы, выполненной по ГОСТу Рисунок 1 – Блок-схема алгоритма № 1 6 Рисунок 2 – Блок-схема алгоритма № 2 b) Инвариант цикла • При начале выполнения цикла количество элементов массива, равных ключевому значению, равно 0. • На каждой итерации цикла, если текущий элемент массива равен ключевому значению, декрементируем количества элементов массива. Если текущий элемент массива не равен ключевому значению, количество элементов массива остается неизменным. 7 • Когда цикл завершается количество элементов, равных ключевому значению, равно количеству элементов, равных ключевому значению, в исходном массиве. • Таким образом, инвариант цикла - количество элементов массива, равных ключевому значению, и он остается неизменны на протяжении всего цикла. Корректность цикла заключается в том, что мы не удаляем элементы массива напрямую, а только уменьшаем счётчик элементов, равных ключевому значению, и оставляем остальные элементы массива без изменений. c) Вычислительная сложность алгоритма используя теоретический подход Для первого алгоритма представлены данные подсчета количества выполняемых алгоритме операторов в табл. 1 Таблица 1 Номер опера- тора Оператор Кол-во выполнений оператора в строке 1 i=1; 1 2 while(i<=n){ n 3 if(x[i]==key){ n 4 for(int j=i;j 𝑛 𝑗=𝑖 5 x[j]=x[j+1]; ∑ 𝑡𝑗 𝑛 𝑗=𝑖 6 } 7 n=n-1 n 8 } 12 } 8 j#$ j#$ j#$ Выведем функцию роста для времени выполнения алгоритма: 𝑇(𝑛) = 1 + 𝑛 + 𝑛 + ∑ 𝑛 𝑡 j + ∑ 𝑡 j + 𝑛 (1) Определим порядок роста в лучшем случае, то есть, когда условный оператор не выполняются (массив не имеет ключевого значения), но условие n раз проверяется (то есть оператор 2 выполниться обязательно). В наилучшем случае сумма ∑ 𝑛 𝑡 j = 0. Подставит этим значения в формулу (1) T(n) = 1+n. Порядок роста времени в зависимости от n наилучшем случае линейный T(n)=n+1. Определим порядок роста в худшем случае, то есть, когда условный оператор 3 выполняется полное количество раз (то сеть все элементы массивы равны ключевому значению). В этом случае в сумме 𝑛 j#$ 𝑡 j значение 𝑡 j равно j. Тогда значение ∑ 𝑛 𝑡 = 𝑛(𝑛&1) = 𝑛 2 &𝑛 j#$ j ) ) Подставим эти значения в формулу (1). Получили порядок роста как арифметическая прогрессия вида T(n)= 𝑛 2 &𝑛 ) Функция 𝑛 ) имеет порядок роста выше, чем функция n. Таким образом, в выражении для T(n) доминирующей функцией является 𝑛 ) , и она определяет порядок роста для алгоритма в худшем случаем. То есть скорость роста – квадратичная. Вывод. Худший и средний случай дают одинаковы порядок роста времени от n. Значит, в целом, скорость роста – квадратичная. Для второго алгоритма представлены данные подсчета количества выполняемых алгоритме операторов в табл. 2 ∑ 9 Таблица 2 Номер опера- тора Оператор Кол-во выполнений оператора в строке 1 j=0 1 2 for(int i=0;i 5 j++; n 6 } 7 } 8 n=j; 1 Выведем функцию роста для времени выполнения алгоритма: 𝑇(𝑛) = 3 ∗ 𝑛 + 3 (2) Определим порядок роста в лучшем случае, то есть, когда условный оператор не выполняется (массив не имеет ключевого значения), но условие n раз проверяется (то есть оператор 2 выполниться обязательно). В наилучшем случае алгоритм выполнится T(n) = 2*n+3.В этом случае скорость роста – линейная. Определим порядок роста в худшем случае, то есть, когда условный оператор 4 выполняется полное количество раз (то есть все элементы массивы равны ключевому значению). В худшем случае алгоритм выполнится T(n)=4*n+3.В этом случае скорость роста – линейная. Определим порядок роста в среднем случае, то есть, когда условный оператор 3 выполняется n/2 повторяется раз (то есть половину элементов массива равен ключевому значению). В среднем случае алгоритм выполнится T(n) = 3*n+1. В этом случае скорость роста – линейная. Вывод. Лучший, худший и средний случай дают одинаковы порядок 10 роста времени от n. Значит, в целом, скорость роста – линейная. 11 2.3 Реализация алгоритма в виде функции Реализация алгоритма на массиве при n = 10, key = 2 см. рис. 3: Исходный массив (n = 10): 1 2 3 2 2 2 5 2 2 2.Результат: n = 3; 1 3 5, подсчет суммарного количества выполненных операций равен 26 для первого алгоритма, для второго равен 10. Рисунок 3 – реализация алгоритма при n = 10 Реализация алгоритма с заполнением массива датчиком случайных чисел и выводом массива на экран монитора n = 100, key = 2 см. рис. 4; Рисунок 4 – реализация алгоритма при n = 10 с заполнением случайных чисел 2.4 Тестирование алгоритма в ситуациях a) Все элементы массива должны быть удалены Рисунок 5 – реализация алгоритма в случае, когда все элементы массива должны быть удалены 12 b) Ни один элемент не удаляется Рисунок 6 – реализация алгоритма в случае, когда ни один элемент не удаляется 13 2.5 Оценка ёмкости сложности алгоритма В данном алгоритме выделяется только константное количество памяти для переменных i, j, n, key и массива x. Поэтому ёмкостная сложность алгоритма оценивается как O(1), т.е константная сложность. 2.6 Вывод по заданию № 1 Первый алгоритм использует цикл while и вложенный цикл for и имеет квадратичную сложность. Второй алгоритм использует только вложенный цикл for и имеет линейную сложность. Таким образом, второй алгоритм является более эффективным, чем первый с квадратичной скоростью, особенно на больших объемах данных. 2.7 Реализация структурированного кода программы с комментариями на основе блок-схемы Рисунок 7 – реализация первого алгоритма на ЯП c++ 14 Рисунок 8 – реализация второго алгоритма на ЯП c++ 15 3 ЗАДАЧА №2 3.1 Формулировка задачи Персональный вариант №8. Найти восходящую диагональ матрицы с максимальной суммой элементов. 3.2 Математическая модель решения задачи Блок-схема алгоритма: Рисунок 9 – Блок-схема алгоритма 16 Рисунок 10 – Блок-схема алгоритма 17 Рисунок 11 – Блок-схема алгоритма Рисунок 12 – Блок-схема алгоритма 18 3.3 Реализация алгоритма Рисунок 13 – реализация алгоритма на ЯП C++ 19 Рисунок 14 - реализация алгоритма на ЯП C++ Рисунки 15 - реализация алгоритма на ЯП C++ 20 3.4 Тестирование алгоритма Входные данные Ожидаемы выходные данные Фактические выходные данные 1 1 1 1 2 3 4 5 5 1 2 3 4 5 6 7 8 11 11 3.5 Выполнение практической оценки сложности Для n = 100 и m = 100 скорость алгоритма равна 1.175 секунд, а скорость алгоритма для n = 100 и m = 1000 скорость алгоритма равна 11.503 секунд. Стоит сказать, что данные массивы заполнялись автоматически случайными элементами до 100, поэтому данные о времени будут корректны только для данного промежутка чисел. Если мы захотим увеличить значение чисел, то время работы также будет увеличиваться. 3.6 Оценить ёмкостную сложность алгоритма Алгоритм состоит из трёх циклов for, с вложенными циклами, каждый из которых отвечает за нахождение восходящей диагонали с максимальной суммой элементов в своей части матрицы. Когда найдены диагонали с максимальной суммой элементов в каждой из трёх частей они сравниваются и выводится максимальная сумма элементов, а также сами элементы матрицы. Таким образом ёмкостная сложность алгоритма зависит от размерности матрицы. 21 3.7 Результаты выполнения алгоритма Рисунок 16 – результат выполнения алгоритма при n = 5 и m = 5 Рисунок 17 - результат выполнения алгоритма при n = 5 и m = 10 3.8 Вывод Алгоритм нахождения восходящей диагонали матрицы с максимальной суммой элементов, который я разработал для выполнения данной работы является эффективным, так как он просматривает каждый элемент матрицы ровно один раз, что позволяет нам использовать его для матриц больших размерностей. 22 |