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