Сложность алгоритма

Лекция 12 Сложность алгоритма Встречаются ситуации, когда существует конечный алгоритм решения задачи, но практическое его использование бессмысленно. Это, как правило, связано с большим объемом вычислений, а значит и с длительным временем ожидания ответа. Пусть Al – некоторый алгоритм. Определим функцию равную числу элементарных шагов алгоритма Al, применённого к входу X. Функция называется временной сложностью алгоритма Al. Следует отметить, что понятие элементарный шаг алгоритма и временная сложность алгоритма зависят от модели вычислений. Например, элементарный шаг нормального алгорифма Маркова состоит в поиске вхождения слова с последующей его заменой, а элементарный шаг машины Тьюринга в совершении перехода из одной вершины графа в другую. К сожалению, даже для простейших алгоритмов, выписать функцию очень трудно, а в ряде случаев невозможно, поскольку она зависит от слишком многих параметров. Например: рассмотрим алгоритм умножения столбиком, а в качестве модели вычисления возьмем школьника, знающего таблицу умножения. Умножение на степень 10 требует меньше элементарных операций, чем обычно. Поэтому, трудоемкость алгоритма исследуется в зависимости от длины входной информации. Обозначим через множество входных слов алгоритма длины . Для получения требуемой зависимости используются следующие подходы. 1. Гарантированный результат (оценка в худшем случае) 2. Среднее значение . 3. Вероятностная оценка , где - вероятность входа x. Среднее значение является частным случаем вероятностной оценкой, при одинаковых вероятностях входов. Наиболее употребительным является первый подход. Кроме временной сложности алгоритма часто рассматривают емкостную сложность алгоритма. Под емкостной сложностью алгоритма понимается размер памяти, используемый этим алгоритмом. Конечно же, понятие емкостной сложности алгоритма зависит от конкретной модели. В машине Тьюринга под емкостной сложностью естественно понимать количество ячеек, которые обозревались в процессе работы алгоритма. Емкостная сложность алгоритма, при использовании в качестве модели вычислений нормальных алгорифмов Маркова, это - максимальная длина слова, возникающего в процессе применения схемы нормального алгорифма к входному слову. Обозначим через емкостную сложность алгоритма, примененного к входу x. Получить явное описание функции во многих случаях невозможно в силу слишком большого количества параметров. Поэтому, емкостная сложность исследуется в зависимости от длины входа. Для получения требуемой зависимости используют подход «оценка в худшем случае» . Отметим, что емкостная сложность в модели алгоритма Тьюринга не может превосходить временной сложности алгоритма в худшем случае. Теорема. Пусть емкостная сложность алгоритма Al (в модели Тьюринга) - . Тогда, либо алгоритм не применим к входу x, либо его трудоемкость на входе x длины равна , где c – некоторая константа, зависящая только от алгоритма. Доказательство. Пусть k количество букв в алфавите, включая пустой символ, а r – число различных состояний алгоритма. Поведение алгоритма полностью определяется словом, записанным на ленте, положением универсального считывающего устройства и состоянием, в котором находится алгоритм. Если в процессе вычисления, в какие то моменты времени все эти параметры совпадают, то значит алгоритм «зацикливается». Если происходит зацикливание, то алгоритм Al не применим к входу x. Пусть алгоритм не «зацикливается». В ячейках в каждый момент времени может быть записано одно из слов, универсальное считывающее устройство может просматривать только одну из ячеек, а алгоритм может находиться в одном из r состояний. Таким образом, существует не более возможностей, когда тройки «слово на ленте, положение универсального считывающего устройства, состояние алгоритма» различны. Следовательно, трудоемкость алгоритма Al не превосходит , где выбор константы c удовлетворяет неравенству (в частности можно положить ). Понятие эффективного алгоритма. Будем говорить, что функция есть , если существует константа c, что для всех . Алгоритм называется полиномиальным, если его временная сложность есть , где - некоторый полином. Алгоритмы, временная сложность которых не поддается подобной оценке, называются «экспоненциальными». Различие между этими двумя типами алгоритмов особенно проявляются при решении задач большой размерности. В таблице приведено время счёта задач на компьютере, быстродействие которого - миллиард операций в секунду. функция n=10 n=20 n=30 n=40 n=50 n=60 0,00000001с. 0,00000002с. 0,00000003с. 0,00000004с. 0,00000005с. 0,00000006с. 0,0000001с. 0,0000004с. 0,0000009с. 0,0000016с. 0,0000025с. 0,0000036с. 0,000001с. 0,000008с. 0,000027с. 0,000064с. 0,000125с. 0,000216с. 0,0001с. 0,0032с. 0,0243с. 0,1024с. 0,3125с. 0,7776с. 0,00000102с. 0,001048с. 10,737с. 18,32мин 13 суток 36,5 лет 0,00005905с. 3,48с. 57часов 385,5лет 22.7млн лет 134млрд. лет В следующей таблице приведём максимальные размеры задачи решаемой за один час. Трудоемкость Размеры, решаемые на современных ЭВМ На ЭВМ в 100 раз более быстрых На ЭВМ в 1000 раз более быстрых Эти таблицы демонстрируют причины, по которым полиномиальные алгоритмы являются более предпочтительными, чем экспоненциальные. Эта точка зрения, различающая с одной стороны полиномиальные алгоритмы, а с другой стороны экспоненциальные, является отправным пунктом в определении труднорешаемых задач и теории NP-полных задач. Большинство экспоненциальных алгоритмов – это просто варианты полного перебора, в то время как полиномиальные алгоритмы обычно можно построить лишь тогда, когда удается более глубоко проникнуть в суть решаемой задачи. Имеется широко распространенное соглашение, согласно которому задача не является «хорошо решаемой» до тех пор, пока для ее решения не получен полиномиальный алгоритм. Поэтому, задачу называют «труднорешаемой», если для ее решения не существует полиномиального алгоритма. Следует отметить, что различие между полиномиальными и экспоненциальными алгоритмами может принять совсем иной характер, если размеры решаемых задач невелики. Например, при длине входа алгоритм с трудоемкостью более предпочтителен алгоритма с трудоёмкостью . Более того известны некоторые экспоненциальные алгоритмы, хорошо зарекомендовавшие себя на практике. Дело в том, что временная сложность оценивается в худшем случае, а этих худших случаев может быть немного. В результате, средняя оценка алгоритма (или вероятностная оценка) может быть ограничена полиномом. Примером такого алгоритма может служить симплекс-метод решения задачи линейного программирования. К сожалению, примеры такого рода редки. Хотя экспоненциальные алгоритмы известны для многих задач, не многие из них считаются приемлемыми для практических целей. Сам факт успешного применения экспоненциальных алгоритмов для решения задач, как правило, свидетельствует, что они выявляют некоторые существенные особенности решаемых задач, и, значит, более глубокое исследование может привести к дальнейшему улучшению методов. Заметим, что понятие эффективного алгоритма, оказывается, по сути независимым от способа кодирования исходной задачи. Конечно, речь идет о «естественных» способах кодирования, то есть тех способах кодирования, при которых избыточная информация, содержащаяся в коде задачи – минимальна.