Сложность алгоритма отражает затраты, требуемые для его работы. Будем рассматривать временную сложность. Это функция, которая каждой входной длине n ставит в соответствие минимальное время, затрачиваемое алгоритмом на решение всех однотипных индивидуальных задач этой длины [24].
Из курса математического анализа известно, что функция f(n) есть О(g(n)), если существует константа с такая, что |f(n)|£c(g(n)) для всех n³0 [19].
O(n) – сложность порядка n, n – параметр исходных данных алгоритма. O(n2) – сложность порядка n2. Сложность бывает минимальной, средней и максимальной.
Сложностью задачи называется сложность наилучшего алгоритма.
Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна О(Р(n)), где Р(n) – некоторая полиномиальная функция от входной длины n. Алгоритмы, для временной сложности которых не существует такой оценки, называются экспоненциальными.
Задача считается труднорешаемой, если для нее не существует разрешающего полиномиального алгоритма.
|
|
Итак, основные классы сложности таковы:
а) Полиномиальная сложность.
P(n) – полином от n.
O(P(n)) – сложность задач класса Р.
Полиномиальные задачи: степень полинома не зависит от n.
Например: O(P(n)) – линейная, O(P(n2)) – квадратичная, O(P(n3)) – кубическая.
Такие задачи легко решаются на ЭВМ.
б) Экспоненциальная сложность.
O(xn) – класс Е – экспоненциальный.
Например: O(2n) – построение булеана, O(22n) – нахождение всех переключательных функций от n переменных. При больших n задача становится практически нерешаемой.
в) NP сложные задачи [36].
Вспомним задачу коммивояжера из теории графов. Перебор всех маршрутов в графе из n вершин требует рассмотрения n! вариантов. Однако, n! растет даже быстрее, чем 2n.
В так называемом недетерминированном алгоритме (существует и недетерминированная машина Тьюринга) варианты выбираются случайным образом, тогда, если повезет, можно относительно быстро найти вариант, удовлетворяющий заданным ограничениям [36]. Такие задачи, имеющие недетерминированное решение, которое иногда удается найти за полиномиальное время называются NP-сложными (Nondeterministic Polynomial).
Преобладает мнение, что детерминированных алгоритмов решения таких задач не существует. Для сокращения перебора вариантов при решении таких комбинаторных задач (задач комбинаторной сложности) предлагаются различные способы «борьбы с перебором, борьбы с проклятием размерности» [9-10]. В эвристических алгоритмах используют для этого некоторую дополнительную информацию – эвристики, позволяющие находить решения, лишь на 10-15 % хуже оптимальных. Тем не менее, NP сложные задачи не имеют гарантированных оценок времени решения. Даже незначительное изменение исходных данных приводит к его резкому увеличению.
|
|
Поэтому иногда говорят, что проблема NP полна, что означает ничтожно малую вероятность существования эффективного (полиномиального) алгоритма.
В настоящее время активно развивается направление так называемых генетических алгоритмов. Это направление использует в борьбе с перебором вариантов опыт развития природы и человека. При этом применяется и соответствующая терминология: «популяция» – некоторое множество вариантов; «скрещивание» вариантов путем определенного комбинирования «хромосом особей» из исходной популяции и получение «потомков»; «эволюция» с целью получения лучших решений.