Структуры данных и модели вычислений

         

Об измерении алгоритмической сложности задач


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

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

Вопрос о нахождении сложностных характеристик задач весьма труден. Трудности, как правило, связаны с логической сложностью рассматриваемых задач и обилием алгоритмов в любом универсальном классе.

Рассмотрим некоторые подробности на примере тьюринговых программ. Будем считать, что задача представлена двухместным словарным предикатом над некоторым алфавитом и заключается в нахождении по заданному слову

слова такого, что истинно.

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

Результат работы тьюринговой программы на входном слове

обозначим , считая равным выходному слову.

Будем говорить, что тьюрингова программа решает задачу , если на любом входном слове она останавливается через конечное число шагов и .

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

Величину будем называть временем работы программы на слове . В большинстве случаев эта величина существенно зависит от длины слова , поэтому представляет интерес функция , где максимум вычисляется по всем словам длины .

Заметим, что эта ситуация не является общей; в некоторых случаях величина не зависит от длины слова . Например, пусть требуется определить четность числа, представленного в двоичном коде. Для этого достаточно посмотреть на его младший разряд.



Содержание  Назад  Вперед