11.1. Анализ алгоритмов

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

При анализе алгоритма определяется количество времени, необходимое для его выполнения на ЭВМ. Это приблизительное количество времени, затраченное на выполнение стандартных или приведенных к ним операций, выполняемых алгоритмом. Тогда вычислительная сложность алгоритма обычно называется «временем работы алгоритма».

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

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

В настоящее время алгоритмы сравниваются по скорости роста числа операций. Это связано с тем, что при небольшом размере (n < 50) входных данных одному алгоритму потребуется меньше операций, чем другому. При росте объема входных данных (n > 50) для указанных алгоритмов ситуация может поменяться на противоположную. На основе анализа алгоритмов оценивается, насколько быстро решается задача на массиве входных данных размера n. Следовательно, анализ алгоритма позволяет пользователю выбирать эффективный с его точки зрения алгоритм.

При анализе алгоритмов решения сложных задач (n > 1000) для упрощения различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве. Такое разбиение позволяет уменьшить число рассматриваемых возможностей. Например, число различных расстановок множества из 20 неповторяющихся чисел есть 20! = 2432902008176640000.

Применим к данному множеству из 20 чисел алгоритм поиска наименьшего элемента. Как уже было сказано, имеется 2432902008176640000 вариантов расстановки чисел в начальном множестве. Их все можно поместить в один класс. Количество вариантов, когда наименьшее число стоит на втором месте, в 20 раз меньше, а именно 19! = 121645100408832000. Их можно отнести к другому классу. Таким образом, можно разбить все входные множества на N разных классов. Для описанного алгоритма разбиение основывается на местоположении элемента, имеющего наименьшее значение. В результате получается 20 классов. После выделения классов можно проанализировать поведение алгоритма на одном множестве из каждого класса. Это разбиение выполняется на основе принципа «разделяй и властвуй», приведенного выше. Если разбиение выбрано правильно с точки зрения пользователя, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций будет другим.

В алгоритмах обычно выделяют операции двух типов:

- сравнение;

- арифметические операции:

• аддитивные операторы;

• мультипликативные операторы.

Существует тезис Тьюринга: любой алгоритм может быть реализован на машине Тьюринга. Математически доказано, что если задача не может быть решена на машине Тьюринга, то она не может быть решена ни на какой другой автоматической вычислительной машине.

Один из основных результатов Тьюринга — разделение всех задач, решаемых с помощью алгоритмов, на два типа (класса).

1 класс. Задачи, для которых алгоритмы никогда не могут быть написаны, т.е. задачи в принципе не решаемые. Например, задача о квадратуре круга или построение универсального решателя (алгоритма) для решения всех задач.

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

2 класс. Это класс решаемых задач, т.е. задач, для которых могут быть написаны и реализованы алгоритмы. К ним относятся задачи, решаемые на основе:

• полиномиальных алгоритмов;

• экспоненциальных алгоритмов.

Экспоненциальными алгоритмами называются алгоритмы, у которых время решения экспоненциально растет по мере увеличения размера входных данных. К ним относятся алгоритмы типа 2ⁿ, n!, n!! и т.п. Здесь n — количество входов алгоритма.

К экспоненциальным алгоритмам относятся алгоритмы полного перебора при нахождении оптимального решения.

Пример 1. Найти все одинаковые числа в массиве натуральных чисел размера n  n.

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

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

Полиномиальные алгоритмы - это такие алгоритмы, при реализации которых на ЭВМ, время решения изменяется в зависимости от размера входных данных (например, числа вершин или ребер графа). Эта зависимость представляется в виде полиномов, где число входов n принимает значения n, n², n³, ... Если число входов равно n, то имеем дело с «линейным» алгоритмом. Линейный алгоритм - это алгоритм, у которого зависимость времени решения от числа входных данных носит линейный характер. Другими словами, полиномиальные алгоритмы – это алгоритмы, у которых время решения находится в полиномиальной зависимости от изменения размера входных данных.

Пример 3. Пусть время решения произвольного алгоритма находится в следующей зависимости от размера входных данных: t = an + b, где n это числа из множества A = {1, 5, 10, 15, 20, 25, 30}; a, b – постоянные величины (a = 20, b = 10). График временной сложности алгоритма показан на рис. 11.1 (Функция 1).

Пример 4. Пусть время решения произвольного алгоритма находится в следующей зависимости от размера входных данных: t = an² - bn + c, где n - числа из множества A (пример 3); a, b, c – постоянные величины (a = 1, b = 7, c = 10). График временной сложности алгоритма представлен на рис. 11.1 (Функция 2).

Рис. 11.1. Сравнение временной сложности функций

График функции 1 отражает линейную зависимость времени работы алгоритма от числа входных данных, а график функции 2 - квадратичную.

Анализируя графики, видно, что существует некоторая область для входных данных небольшого размера, где временная сложность «квадратичных» алгоритмов лучше, чем линейных. Так, например, на рис. 11.1 видно, что в области, где n меняется от 1 до приблизительно 27, квадратичный алгоритм работает быстрее линейного. Затем (n > 27) линейный алгоритм работает значительно быстрее.

Аппроксимированные графики временной сложности полиномиальных алгоритмов различных классов показаны на рис. 11.2.

Рис. 11.2. Графики временной сложности различных классов алгоритмов

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

Рис. 11.3. Классификация алгоритмов

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

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

Задачей на оптимальность считается задача определения допустимого решения, дающего экстремум функции.

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

Согласно классическому учебнику Кормена, Лейзерсона и Ривеста «Алгоритмы: построение и анализ» запись f(n) = (g(n)) включает в себя две оценки временной сложности алгоритма: верхнюю и нижнюю. Их разделяют на f(n) = O(g(n)) и f(n) = (g(n)).

Говорят, что f(n) = O(g(n)), если найдется такая константа c > 0 и такое число входных данных n₀, что 0  f(n)  cg(n) для всех n  n₀.

Говорят, что f(n) = (g(n)), если найдется такая константа c > 0 и такое число n₀, что 0  cg(n)  f(n) для всех n  n₀.

Здесь предполагается, что функции f и g неотрицательны для достаточно больших значений аргумента.

Асимптотически обозначают, например, 8n⁴ + 5n³ + 13n² + 9n + 4  8n⁴ + (n³) + (n²) + (n)  (n⁴). То есть какой бы ни была функция k(n) = (n³), (n²), (n) в левой части, сумма 8n⁴ + (n³) + (n²) + (n), есть (n⁴). Тогда время работы полиномиальных алгоритмов такого типа составляет не более (n^k), для некоторой константы, не зависящей от длины входа.

В теории встречаются задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(n^k) ни для одного фиксированного числа k. Согласно работе Кормена, Лейзерсона и Ривеста «Алгоритмы: построение и анализ» полиномиальные алгоритмы представляют собой некую границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес.

Отдельный класс составляют задачи, называемые «NP-полными». Для них не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с нерешенными проблемой Р = NP или Р ≠ NP. Сокращение NP происходит от английских слов Nondeterministic Polynomial time, что переводится как недетерминированное полиномиальное время.

Большинство специалистов полагают, что NP-полные задачи нельзя решить за полиномиальное время. Очевидно, что если хотя бы для одной NP-полной задачи существует решающий ее полиномиальный алгоритм, то и для всех NP-полных задач такие алгоритмы существуют. В настоящее время известно много NP-полных задач. На практике считают, что если для некоторой задачи удается доказать ее NP-полноту, то она является практически неразрешимой.

В теории алгоритмов при исследовании NP-полноты рассматриваются в основном задачи разрешения, то есть задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально задачу разрешения можно рассматривать как функцию, отображающую множество условий I в множество решений S = {0, 1}, где (1 = «да», 0 = «нет»). В этой связи для определения NP-полноты многие задачи преобразуют к указанному виду.

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

Поэтому данные задачи выделяют в особый класс оптимизационных комбинаторных задач на графах. В задачах такого класса общее число вариантов решения равно числу перестановок из n вершин графов, то есть C_n = n!, а с учетом ограничений на формирование подмножеств (частей графа в задаче разбиения) – числу сочетаний из n вершин по m частей, то есть = n! / m!(n – m)!

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

Говорят, что алгоритм решает задачу за время O(T(n²)), если на входном данном, например битовой строке i длины n, алгоритм работает за время O(T(n²)).

Говорят, что функция f:{0, 1}  {0, 1} вычислима за полиномиальное время, если существует полиномиальный алгоритм, который для любого элемента y  {0, 1} выдает результат f(y).

Интуитивно класс Р можно представлять себе как класс задач, которые можно “быстро” решить, а класс NP — как класс задач, которые нельзя решить за полиномиальное время. Известно, что ни для одной NP-полной задачи не найден полиномиальный разрешающий алгоритм.

Конечно, нет уверенности, что однажды не будет найден полиномиальный алгоритм для решения NP-полной задачи, это и будет доказательством, что Р = NP.