Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №18. Решение задач на определение сложности алгоритмаЦель работы: Получение навыков определения сложности алгоритмов сортировки. Алгоритм сортировки Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Оценка алгоритма сортировки Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти: Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это  [1] и плохое поведение — это  . Идеальное поведение для упорядочения —  . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в  сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью  , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за  операций. При этом число n должно быть заранее известно;Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют  памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет  ). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.Классификация алгоритмов сортировки Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет , но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки. Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. Объём данных не позволяет им разместиться в ОЗУ. Также алгоритмы классифицируются по: потребности в дополнительной памяти или её отсутствии потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой Список алгоритмов сортировки В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей. Алгоритмы устойчивой сортировки Сортировка пузырьком (англ. Bubblesort ) — сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сортировка перемешиванием (Шейкерная, Cocktail sort, bidirectional bubble sort) — Сложность алгоритма: O(n2) Гномья сортировка — имеет общее с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — O(n2). Сортировка вставками (Insertion sort) — Сложность алгоритма: O(n2); определяем где текущий элемент должен находиться в упорядоченном списке и вставляем его туда Блочная сортировка (Корзинная сортировка, Bucket sort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций "переставить" и "сравнить". Сортировка подсчётом (Counting sort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти (рассмотрено 3 варианта) Сортировка слиянием (Merge sort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки Сортировка с помощью двоичного дерева (англ. Treesort) — Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти Алгоритмы неустойчивой сортировки Сортировка выбором (Selection sort) — Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка Сортировка Шелла (Shell sort) — Сложность алгоритма: O(n log2 n); попытка улучшить сортировку вставками Сортировка расчёской (Comb sort) — Сложность алгоритма: O(n log n) Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка Плавная сортировка (Smoothsort) — Сложность алгоритма: O(n log n) Быстрая сортировка (Quicksort) — Сложность алгоритма: O(n log n) — среднее время, O(n2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине Introsort — Сложность алгоритма: O(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n). Patience sorting — Сложность алгоритма: O(n log n + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность Stooge sort — рекурсивный алгоритм сортировки с временной сложностью  .Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти. Цифровая сортировка — то же, что и Поразрядная сортировка. Непрактичные алгоритмы сортировки Bogosort — O(n·n!) в среднем. Произвольно перемешать массив, проверить порядок. Сортировка перестановкой — O(n·n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. Глупая сортировка (Stupid sort) — O(n3); рекурсивная версия требует дополнительно O(n2) памяти Bead Sort — O(n) or O(√n), требуется специализированное аппаратное обеспечение Блинная сортировка (Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение Алгоритмы, не основанные на сравнениях Блочная сортировка (Корзинная сортировка, Bucket sort) Лексикографическая или поразрядная сортировка (Radix sort) Сортировка подсчётом (Counting sort) Остальные алгоритмы сортировки Топологическая сортировка Внешняя сортировка Пример Сортировка простым включением. Предположим, что на некотором этапе работы алгоритма левая часть массива с 1-го по (i — 1)-й элемент включительно является отсортированной, а правая часть с i-го по n-й элемент остается такой, какой она была в первоначальном, неотсортированном массиве. Очередной шаг алгоритма заключается в расширении левой части на один элемент и, соответственно, сокращении правой части. Для этого берется первый элемент правой части (с индексом i) и вставляется на подходящее ему место в левую часть так, чтобы упорядоченность левой части сохранилась. Процесс начинается с левой части, состоящей из одного элемента А[1], а заканчивается, когда правая часть становится пустой.    Оценим сложность алгоритма сортировки простым включением. Очевидно, что временная сложность зависит как от размера сортируемого массива, так и от его исходного состояния в смысле упорядоченности элементов. Временная сложность будет минимальной, если исходный массив уже отсортирован в нужном порядке значений ключа (в данном случае — по возрастанию). Максимальное значение сложности будет соответствовать противоположной упорядоченности исходного массива, т.е. упорядоченности исходного массива по убыванию значений ключа. Обычно для алгоритмов сортировки временная сложность оценивается количеством пересылок элементов. Оценим величину минимальной временной сложности алгоритма. Если массив уже отсортирован, то тело цикла while не будет выполняться ни разу. Выполнение процедуры сведется к работе следующего цикла:  Поскольку тело цикла for исполняется n — 1 раз, то число пересылок элементов массива Мmin = 2(n - 1), а число сравнений ключей равно Сmin = n - 1. Сложность алгоритма будет максимальной, если исходный массив упорядочен по убыванию. Тогда каждый элемент А[i] будет «прогоняться» к началу массива, т.е. устанавливаться в первую позицию. Цикл while выполнится 1 раз при i = 2, 2 раза при i = 3 и т. д., п — 1 раз при i = п. Таким образом, общее число пересылок записей равно:  Более подходящей для реальной ситуации является средняя оценка сложности. Для ее вычисления надо предположить, что все элементы исходного массива — случайные числа и их значения никак не связаны с их номерами. В таком случае результат очередной проверки условия x. key Разумно допустить, что среднее число выполнений цикла While для каждого конкретного значения i равно i/2, т. е. в среднем каждый раз приходится просматривать половину последовательности до тех пор, пока не найдется подходящее место для очередного элемента Тогда формула для среднего числа пересылок (средняя оценка сложности) будет следующей:  Как максимальная, так и средняя оценка сложности алгоритма квадратична (является полиномом второй степени) по параметру n — размеру сортируемого массива. |