Об измерении алгоритмической сложности задач
При практическом решении многих интересных задач с помощью вычислительных автоматов существенную роль играет время работы и объем памяти, которые требуются для их решения соответствующими алгоритмами. Упомянутые характеристики называются, соответственно, временной и пространственной сложностью алгоритма.
Временной и пространственной сложностью задачи в классе алгоритмов (или автоматов) называется время и объем памяти, необходимые "лучшему" в данном классе алгоритму (автомату) для решения рассматриваемой задачи.
Вопрос о нахождении сложностных характеристик задач весьма труден. Трудности, как правило, связаны с логической сложностью рассматриваемых задач и обилием алгоритмов в любом универсальном классе.
Рассмотрим некоторые подробности на примере тьюринговых программ. Будем считать, что задача представлена двухместным словарным предикатом над некоторым алфавитом и заключается в нахождении по заданному слову
слова такого, что истинно.
Слово будем считать решением задачи при входном слове . Чтобы пустоту слова трактовать как отсутствие решения, наложим на следующие ограничения:
Результат работы тьюринговой программы на входном слове
обозначим , считая равным выходному слову.
Будем говорить, что тьюрингова программа решает задачу , если на любом входном слове она останавливается через конечное число шагов и .
Через обозначим число элементарных тьюринговых команд, которые будут выполнены программой от начального момента до момента остановки при работе на входном слове . Если при входном слове программа выполняет бесконечное число шагов, то считаем .
Величину будем называть временем работы программы на слове . В большинстве случаев эта величина существенно зависит от длины слова , поэтому представляет интерес функция , где максимум вычисляется по всем словам длины .
Заметим, что эта ситуация не является общей; в некоторых случаях величина не зависит от длины слова . Например, пусть требуется определить четность числа, представленного в двоичном коде. Для этого достаточно посмотреть на его младший разряд.
Важным и интересным для практики является вопрос о верхних и нижних оценочных функциях для времени работы конкретных алгоритмов.
Заметим, что получение нижних нетривиальных оценок каждый раз представляет собой сложную математическую задачу. Известно, например, что временная сложность задачи распознавания симметрии слова тьюринговыми программами оценивается снизу функцией , где — длина слова, а — некоторая константа.
Для многих интересных с практической точки зрения задач известные верхние оценки носят экспоненциальный характер, что часто свидетельствует о больших затратах времени при выполнении соответствующих алгоритмов на вычислительных установках.
Если для задачи имеется полиномиальная от
верхняя оценочная функция, то говорят, что разрешима в полиномиальное время.
Для многих задач не удается установить существование верхних полиномиальных оценочных функций. Однако при этом распознавание на паре слов , , является ли слово решением задачи на входе , решается за полиномиальное от длины слова время и, кроме того, для каждого существует ответ , длина которого ограничена некоторым полиномом от длины . Это так называемые задачи с проверяемым за полиномиальное время ответом. Такой задачей является, например, задача о выполнимости булевых формул, которая заключается в следующем. По заданной булевой формуле найти набор значений переменных, при которых соответствующая формуле булева функция принимает значение 1. Имея минимальный программистский опыт, легко убедиться в возможности проверки ответа к этой задаче за полиномиальное время.
Задачи с проверяемым за полиномиальное время ответом называются переборными с гарантированным экспоненциальным перебором. Действительно, пусть такая задача и длина возможного ответа
ограничена полиномом от длины входа , то есть . Пусть, далее — полином, являющийся верхней оценкой времени работы программы, проверяющей ответ, тогда, перебирая всевозможные
слов длины и затрачивая на проверку каждого не более тактов времени, получим алгоритм с верхней оценкой .
