Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
|
Задание Определить сложность алгоритма. Упорядочить массив n целых чисел таким образом, чтобы элементы с четными и нечетными значениями чередовались (пока имеются элементы разной четности). Дополнительные задания Разработать алгоритм быстрой сортировки. Оценить сложность алгоритма. Этот алгоритм был разработан Э. Хоаром. В алгоритме быстрой сортировки используются три идеи: • разделение сортируемого массива на 2 части, левую и правую; • взаимное упорядочение двух частей (подмассивов) так, чтобы все элементы левой части не превосходили элементов правой части; • рекурсия, при которой подмассив упорядочивается точно таким же способом, как и весь массив. Для разделения массива на две части нужно выбрать некоторое «барьерное» значение ключа. Это значение должно удовлетворять единственному условию: лежать в диапазоне значений для данного массива (т.е. между минимальной и максимальной величиной). За «барьер» можно выбрать значение ключа любого элемента массива, например первого, или последнего, или находящегося в середине. Далее нужно сделать так, чтобы в левом подмассиве оказались все элементы с ключом, меньшим барьера, а в правом — с большим: Затем, просматривая массив слева направо, необходимо найти позицию первого элемента с ключом, большим барьера, а просматривая справа налево — найти первый элемент с ключом, меньшим барьера. Следует поменять эти значения, затем продолжить встречное движение до следующей пары элементов, предназначенных для обмена. Необходимо повторять эту процедуру, пока индексы левого и правого просмотров не совпадут. Место совпадения станет границей между двумя взаимно упорядоченными подмассивами. Далее алгоритм рекурсивно применяется к каждому из подмассивов (левому и правому). В конечном счете приходим к совокупности из п взаимно упорядоченных одноэлементных массивов, которые делить дальше невозможно. Эта совокупность образует один полностью упорядоченный массив. Сортировка завершена! Лабораторная работа № 18 Определение сложности работы алгоритма Цель: Изучение определения сложности работы алгоритма Задание 1. Изучите теоретические сведения Теоретические сведения Теория сложности алгоритмов Сложность алгоритма - характеристика алгоритма, определяющая зависимость времени выполнения программы, описывающей этот алгоритм, от объёма обрабатываемых данных. Сложность можно оценить по содержанию программы. Так, если в программе выполняется вложенный цикл с числом шагов внешнего цикла m и вложенного цикла n, то сложность будет пропорциональна mn. Формально определяется как порядок функции, выражающей время работы алгоритма. Эффективность алгоритма – временная сложность в самом худшем случае O(f(n)) или просто f(n). Функция от n f(n) равна максимальному числу шагов, выполняемых алгоритмом и имеет порядок роста O(f(n)), причём максимум берётся по всем входным данным длины n. Существует константа c, такая, что для достаточно больших n величина c•f(n) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины n. Анализ рекурсивных программ значительно сложнее обычных, так как зачастую требуется решать дифференциальные уравнения. Для их анализа необходимо применять методы похожие на методы решения дифференциальных уравнений. При анализе рекурсивных процедур составляются рекуррентные соотношения, которые получают исходя из структуры рекурсивного алгоритма, отражающие характер рекурсивного вызова алгоритма и зависящие от величины входных данных. Решение рекуррентных соотношений Существуют 3 способа решения рекуррентных соотношений: Находится функция f(n), которая мажорирует T(n) для всех значений n, т.е. для всех n выполняется неравенство T(n)<=f(n). Иногда только лишь предположительно определяется вид функции f(n), зависящей от некоторых неопределённых параметров. Далее подбираются такие параметры, что для всех n будет выполняться T(n)<=f(n). Последовательно подставляются в рекуррентное соотношение зависимости T(m), где m<n, так, чтобы из правой части были исключены все T(m) с m>1, оставив толь ко T(1). Но так как T(1) всегда является константой, то получится под конец зависимость от констант и n. Использование общих решений. Оценка решений рекуррентных соотношений Рассмотрим пример процедуры-функции mergesort сортировки слиянием, входные данные которой – это список элементов длиной n, а выходные – это отсортированный список. Эта функция так же использует процедуру слияния merge, входные данные которой – это два отсортированных списка L1 и L2. Данная процедура просматривает эти списки поэлементно, начиная с больших. На каждом шаге наибольший элемент из двух сравниваемых удаляется из своего списка и помещается в выходные данные. Получается тем самым единый отсортированный список, содержащий все элементы L1 и L2. Процедура на списках merge, длиной n/2, выполняется за время порядка O(n). function mergesort(L:LIST; n:integer):LIST;{L - список типа LIST длиной n, где n является степенью числа 2} var L1,L2:LIST; begin if n=1 then return(L) else begin разбиение L на две части L1 и L2, каждая длиной n/2; return(merge(mergesort(L1, n/2),(mergesort(L2, n/2))); end; end; {mergesort} Пусть T(n) - время выполнения процедуры mergesort в самом худшем случае. Анализируя текст программы, запишем рекуррентное неравенство, которое ограничивает сверху T(n):  (7.1)В данном неравенстве c1 – это количество шагов выполняемых алгоритмом над списком L длиной 1. Время работы процедуры можно разбить на две части, если n>1. Первая часть состоит из: 1) проверки n<>1, 2) разбивки L, на две равные части и 3) вызова процедуры merge. Эти три операции требуют или фиксированное время для выполнения первой части или пропорционального n для второй и третьей. Следовательно, можно выбрать такую константу c2, которая будет создавать ограничение для выполнения данной части процедуры равное c2*n. Вторая часть процедуры mergesort состоит из двух рекурсивных вызовов этой процедуры для списков длины n/2, которые будут требовать время 2T(n/2). Так было получено второе неравенство. Формулу верхней границы в замкнутой форме можно получить лишь, если n является степенью числа 2. При выполнении этого условия T(n) можно оценить для любых n. Другими словами, если n лежит в промежутке  , то значение T(n) располагается между T(2i)…T(2i+1). Нетрудно заметить, что выражение 2T(n) можно заменить на T((n+1)/2)+T((n-1)/2) для нечётных n>1. Таким образом, можно найти решение рекуррентного соотношения в замкнутой форме для любых n. Замкнутая форма - это вид функции T(n), не включающей в себя никаких выражений T(m) для m<n.Произведём оценку рекуррентного соотношения (7.1). Заменим в этом соотношении n на n/2 и получим  (7.2)Подставим правую часть (7. 2) в (7. 1)  (7.3)Заменяя аналогичным образом в (7. 1) |