- •Глава 1. Основы анализа алгоритмов §1. Интуитивное понятие алгоритма и его уточнение
- •§2. Меры сложности алгоритмов
- •§3. Асимптотический анализ оценки сложности алгоритмов
- •§4. Свойства асимптотических оценок функций.
- •Если и , то , т. Е.
- •§5. Практический анализ эффективности программ.
- •§6. Анализ рекурсивных программ. Рекуррентные отношения.
- •§7. Стратегия декомпозиции. Анализ сложности алгоритмов декомпозиции.
- •I. Мультипликативные управляющие функции
- •II. Другие управляющие функции.
§2. Меры сложности алгоритмов
Размером задачи называется некоторая мера количества входных данных задачи. Например, число строк/столбцов матрицы; количество ребер графа и т.д.
Для оценки сложности алгоритмов существует много критериев. Чаще всего сложность алгоритма – количество необходимых для решения задачи ресурсов как функция от ее размера.
Рассматриваются различные меры сложности в зависимости от вида ресурса. Рассмотрим некоторые из них:
Временная сложность алгоритма – «время» выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма, которые необходимо выполнить для достижения результата)
Емкостная сложность алгоритма – необходимый для работы алгоритма объём памяти машины.
Схемная сложность алгоритма – минимальный размер схемы из функциональных элементов, вычисляющей заданную (булеву) функцию .
Коммуникационная сложность алгоритма – минимальное число бит, которыми нужно обменяться участникам вычисления некоторой функции . Замечания:
а) применяя специальные методы кодирования алгоритма, его можно представить как вычисление некоторой функции с аргументами из множества и с аргументами .
б) понятие схемы функциональных элементов – см. курс математической логики и теории алгоритмов.
в) размером схемы называется количество присваиваний в схеме.
г) коммуникационная сложность играет роль в случаях, когда задача решается объединенными усилиями нескольких участников, соединенных локальной сетью. Возникают ограничения по пропускной способности сети и стоимости трафика.
В дальнейшем будем подробно рассматривать вычисление временной сложности алгоритмов. Этот критерий является важным, но не единственным при оценке эффективности алгоритмов. Например, в силу следующих соображений
Эффективный по времени алгоритм может быть неэффективным по объему памяти.
Эффективные по времени, но сложные алгоритмы нежелательны, если готовые программы будут поддерживать лица, не участвовавшие в их написании.
В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.
Если программа будет использована только несколько раз, стоимость её написания превосходит стоимость времени ее выполнения. Финансово более выгоден алгоритм простой в реализации.
Массовой задачей называется совокупность задач единой структуры.
Пусть дана некоторая массовая задача и алгоритм для ее решения. Для любой частной задачи обозначим – размер задачи , т.е. количество входных данных задачи .
Через обозначим время работы алгоритма над задачей , измеренное в «шагах» т.е. инструкциях алгоритма.
Единица измерения величины - количество операторов, выполняемых алгоритмом на некотором идеализированном устройстве. Выбор модели такого устройства не имеет принципиального значения для анализа и сравнения временной сложности алгоритмов. Для удобства будем далее рассматривать выполнение алгоритма, записанного на языке Pascal.
Время работы алгоритма над задачей зависит не только от количества входных данных, но и от их характера. Т.е. возможно , но .
Поэтому целесообразно рассмотреть – временная сложность алгоритма в худшем случае, т.е. максимальное время работы алгоритма над задачей размера .
Пример: Массовая задача – упорядочение одномерного массива по возрастанию.
:упорядочение массива (5,4,3,2,1)
:упорядочение массива (4,5,3,1,2)
:упорядочение массива (1,2,3,4,5)
. Для большинства алгоритмов сортировки и . Таким образом, эта формула определяет временную сложность алгоритма в худшем случае.
Замечание: Наиболее объективной мерой сложности алгоритма является – временная сложность в среднем, где берется среднее значение величины по всем . вычисляется сложнее, т.к. требует дополнительных сведений о характере данных задачи.
Асимптотической временной сложностью алгоритма в худшем случае (в среднем) называется характеристика поведения величин при