Анализ сложных алгоритмов

Развитие и совершенствование компьютерной техники повлекло за собой создание разнообразных алгоритмов, обеспечивающих решение многочисленных прикладных задач, причем даже для однотипных задач создавалось (и создается) много алгоритмов (программ). Подобные алгоритмы ранее были названы эквива­лентными. Однако для практики недостаточно знать, что решение некоторой задачи на компьютере в принципе возможно (т.е. проблема алгоритмически разрешима). Исполнение любого алгоритма требует определенного объема памяти компьютера для размещения данных и программы, а также времени центрального процессора по обработке этих данных - эти ресурсы ограничены и, следовательно, правомочен вопрос об эффективности их использования. Таким образом, в самом широком смысле понятие эффективности связано со всеми вычислительными ресурсами, не­обходимыми для работы алгоритма. Однако обычно под «самым эффективным» понимается алгоритм, обеспечивающий наиболее быстрое получение результата, поскольку в практических ситуациях именно ограничения по времени часто являются доминирующим фактором, определяющим пригодность того или иного алгоритма. По этой причине рассмотрим временную сложность алгоритмов.

Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей «размер» конкретной задачи, т.е. объем входных данных, необходимых для ее решения. Такой подход удобен, поскольку сравнительная сложность задач может оцениваться через ее размер. Поскольку описание задачи, предназначенной для решения посредством вычислительного уст­ройства, можно рассматривать в виде слова конечной длины, представленной символами конечного алфавита, в качестве формальной характеристики размера задачи можно принять длину входного слова. Например, если стоит задача определения максимального числа в некоторой последовательности из п элементов, то и размер задачи будет п, поскольку любой вариант входной последовательности можно задать словом из п символов.

Временная сложность алгоритма - это функция, которая каждой входной длине слова п ставит в соответствие максимальное (для всех конкретных однотип­ных задач длиной п) время, затрачиваемое алгоритмом на ее решение.

При этом, безусловно, предполагается, что во всех задачах используется одинаковая схема кодирования входных слов.

Различные алгоритмы имеют различную временную сложность и выяснение того, какие из них окажутся достаточно эффективны, а какие нет, определяется многими факторами. Однако теоретики, занимающиеся разработкой и анализом алгоритмов, для сравнения эффективности алгоритмов предложили простой подход, позволяющий прояснить ситуацию. Речь идет о различии между полиномиальными и экспоненциальными алгоритмами.

Полиномиальным называется алгоритм, временная сложность которого выражается некоторой полиномиальной функцией размера задачи п.

Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными.

Различие между указанными двумя типами алгоритмов становятся особенно заметными при решении задач большого размера., Время обработки экспоненциальных алгоритмов при одинаковых размерах задач (превышающих 20) намного выше, чем у полиномиальных; во-вторых, скорость нарастания времени обработки с увеличением размера задачи у экспоненциальных алгоритмов значительно выше, чем у полиномиальных. Различие между обоими типами алгоритмов проявляются еще более убедительно, если проанализировать влияние увеличения быстродействия компьютера на время исполнения алгоритма. В таблице показано, насколько возрастают размеры наибольшей задачи, решаемой за единицу машинного времени, если быстродействие компьютера вырастет в 100 и 1000 раз. Из таблицы видно, что, например, для экспоненциального алгоритма с функцией сложности f(n)=2^a рост скорости вычислений в 1000 раз приводит лишь к тому, что размер наибольшей задачи возрастает всего на 10 единиц, в то время как для функции f(n)^n⁵ она возрастает почти в 4 раза. подобно тому, как существуют алгоритмически неразрешимые задачи, существуют и задачи объективно сложные, т.е. такие, трудоемкость которых невозможно уменьшить совершенствованием компьютера. Задача считается труднорешаемой, если для нее не удается построить полиномиального алгоритма. Это утверждение не является категорическим, поскольку известны задачи, в которых достаточно эффективно работают и экспоненциальные алгоритмы. Примером может служить симплекс-метод, который

успешно используется при решении задач линейного программирования, имея функцию сложности f(n)=2^a. Однако подобных примеров не очень много, и общей следует признать ситуацию, что эффективно исполняемыми можно считать полиномиальные алгоритмы с функциями сложности п_у п или п. Например, при решении задачи поиска нужного данного из п имеющихся в худшем варианте сложность равна п; если же оценить среднюю трудоемкость (продолжительность поиска), то она составит (п + 1)12 - в обоих случаях функция сложности оказывается линейной п. Задача ранжирования, т.е. расстановки в заданном порядке п однотипных данных приводит к полиному 2-й степени; сложность задачи вычисления определителя системы п линейных уравнений с п неизвестными характеризуется полиномом 3-й степени. Повышение быстродействия элементов компьютера уменьшает время исполнения алгоритма, но не уменьшает степень полинома сложности. Следовательно, решению практической задачи на компьютере должна предшествовать оценка ее сложности и доказательство того, что задача решаема за приемлемое время.

Вычислить точное время работы алгоритма оказывается невозможным. Это время помимо всего прочего зависит от характеристик реальной ЭВМ, на которой выполняется программа. Обычно время выполнения алгоритма считают приближенно. Более того, формулы для времени работы обьмно содержат некоторые числовые константы, значение которых можно определить лишь опытным путем. Даже такие оценки позволяют довольно часто выбрать один наилучший алгоритм. В других же случаях с помощью оценок времени работы можно отбросить заведомо медленные алгоритмы, а лучший из оставшихся выбрать с помощью измерения фактического времени работы программ. Остановимся на вопросе о выборе такой характеристики исходных данных, которая определяла бы время работы программы. Эта характеристика называется размером задачи. Для разных задач на время решения влияют разные свойства исходных данных. Так, для задач типа поиска минимума или упорядочивания заданных чисел, где каждое число рассматривается как единое целое, размером задачи является количество исходных чисел. Для задачи разложения на простые сомножители размером естественно считать величину числа. Выбор размера задачи основан на некотором, хотя бы общем представлении об алгоритме решения.

Следующий важный момент при оценке времени работы - отыскание тех частей программы, выполнение которых занимает основную долю всего времени работы. Известен экспериментальный факт, справедливый для подавляющего большинства программ: основная часть времени работы тратится на выполнение очень небольшой части текста программы. Такая часть программы называется внутренним циклом. Так как с самого начала мы требуем приближенной оценки времени работы, поэтому всей остальной частью программы можно пренебречь. Более детальную информацию о времени работы можно получить по результатам измерения фактического времени работы программы для различных исходных данных. С помощью этих экспериментальных данных можно оценить неизвестные постоянные, входящие в формулу

Можно сказать, что алгоритм - это точно определенная (однозначная) последовательность простых (элементарных) действий, обеспечивающих решение любой задачи из некоторого класса.

Однако данное утверждение нельзя принять в качестве строгого определения алгоритма, поскольку в нем использованы другие неопределяемые понятия -однозначность, элементарность и др.

Понятие можно уточнить, указав перечень общих свойств, которые характерны для алгоритмов. К ним относятся:

6. Дискретность алгоритма означает, что алгоритм разделен на отдельные шаги
(действия), причем, выполнение очередного шага возможно только после завершения всех операций на предыдущем шаге. При этом набор промежуточных данных конечен и он получается по определенным правилам из данных предыдущего шага.

7. Детерминированность алгоритма состоит в том. Что совокупность промежуточных величин на любом шаге однозначно определяется системой величин, имевшихся на предыдущем шаге. Данное свойство означает, что результат выполнения алгоритма не зависит от того, кто (или что) его выполняет (т.е. от исполнителя алгоритма), а определяется только входными данными и шагами (последовательностью действий) самого алгоритма.

8. Элементарность шагов: закон получения последующей системы величин из предыдущей должен быть простым и локальным. Какой шаг можно считать элементарным, определяется особенностями исполнителя алгоритма.

9. Направленность алгоритма: если способ получения последующих величин из каких-либо исходных не приводит к результату, то должно быть указано, что следует считать результатом алгоритма.

10. Массовость алгоритма: начальная система величин может выбираться из некоторого множества

О(n) алгоритмы сортировки (например, выбором и вставкой); оценки сложности, лучшие и худшие случаи. О(nlogn) алгоритмы сортировки (например, быстрая сортировка, метод слияния); оценка сложности; другие методы сортировки (метод Шелла и Хоара); сравнение алгоритмов сортировки. Последовательный и бинарный поиск.

Сортировкой называют процесс перегруппировки заданной последовательности объектов в некотором определённом порядке.

Методы внутренней сортировки обеспечивают большую гибкость при построении структур данных и доступа к ним, внешние же методы обеспечивают достижение нужного результата в условиях ограниченных ресурсов.

Методы сортировки служат хорошей иллюстрацией базовых концепций анализа алгоритмов, т.е. оценки качества алгоритмов, что позволяет разумно делать выбор среди, казалось бы, равноценных методов.

Пусть a1,a2,…,an– перестановка множества {1,2,…,n}.

• Если i<j и ai<aj, то пара (ai,aj) называется инверсией перестановки.

• Например, перестановка 3142 имеет 3 инверсии: (3,1) (3,2) (4,2).

• Каждая инверсия – это пара элементов, «нарушающих порядок»; единственная перестановка, не содержащая инверсий, - это рассортированная перестановка 1 2 … n.

• Перестановкой конечного множества называется некоторое расположение его элементов в ряд.

• Перестановки важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки нужно уметь подсчитывать количество перестановок, которые вынуждают повторять некоторый шаг алгоритма определённое число раз.

Рассмотрим внутреннюю сортировку, когда число записей, подлежащих сортировке, достаточно мало, так что весь процесс можно провести в оперативной памяти компьютера, обладающий высоким быстродействием.

В одних случаях может понадобиться физически представлять записи в памяти так, чтобы их ключи были упорядочены; в других можно обойтись вспомогательной таблицей некоторого вида, определяющей перестановку.

Сортировка путём вставки.

(Метод простых вставок или прямого включения) Пусть 1≤j≤N и записи R1,…,Rj-1 уже размещены так, что K1≤K2≤…≤Kj-1.

Будем сравнивать по очереди Kj с Kj-1,Kj-2, … до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri и Ri+1; тогда подвинем записи Ri+1, …,Rj-1 на одну позицию вверх и поместим новую запись в позицию i+1. Удобно совмещать операции сравнения и перемещения.

Поскольку запись Rj как бы «погружается» на положенный ей уровень, этот способ часто называют присваиванием или погружением.

Процесс просеивания может закончиться при выполнении одного из двух условий:

• Найден элемент Rj с ключом, меньшим чем ключ у K

• Достигнут левый конец готовой последовательности.

Словесное описание алгоритма

Записи R1,R2,…,RN пере размещаются на том же месте. После завершения сортировки их ключи будут упорядочены K1≤…≤KN.

• S1. [Цикл по j]. Выполнить шаги от S2 до S5 при j=2,3,…N и после этого завершить выполнение процедуры.

• S2. [установка i, K, R]. Присвоить i←j-1, K←Kj, R←Rj.

• S3. [Сравнение K:Ki]. Если K ≥ Ki, то перейти к S5 (Нашли искомое место для записи R).

• S4. [Перемещение Ri]. Присвоить Ri+1←Ri, i←i-1. Если i>0, то возврат к S3. Если i=0, то K- наименьший из рассмотренных ключей, и К должно занять первую позицию.

• S5. [Перенос R на Rj+1]. Присвоить Ri+1 значение R.

Дата добавления: 2015-07-16