Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Временная и ленточная сложность задач - часть 2


lim T(n)/n=+?

n®? n

Идея доказательства. Покажем, что для любого числа m Î N можно построить Т-машину М2, которая в случае надобности m знаков в M1 сводит к одному знаку и по меньшей мере m шагов вычислений на M1 заменяет постоянным числом шагов вычислений.

Для этого закодируем в виде состояний М2 информацию, как должны интерпретироваться знаки под головками чтения в смысле M1. Чтобы соответствующее число шагов вычислений M1 можно было свести к меньшему числу шагов М2, машина М2  всегда выполняет следующую схему вычислений.

Сначала М2 анализирует ячейки слева и справа от головки. М2 объединяет в один переход все шаги машины M1, которые могут иметь место, пока не остановится M1 или головка машины M1 пройдет область длины 3*m. Эта область представляется тремя знаками в М2, которые находятся слева, справа от головки и под нею. Благодаря этому объединяются, по крайней мере, m шагов m1. Тем самым М2 моделирует самое большее за 8 шагов вычислений (4 для чтения и 4 для записи) по меньшей мере m шагов M1. Для заданного числа с выберем число m, такое, что с*m > 24.

Каждые Т(n) шагов M1 моделируются с помощью 8*[Т(n)/m] шагов М2; кроме того, М2 должна читать свое входное слово и кодировать его. Это даёт n+[n/m] шагов, так что всего получается меньше чем  n+[n/m]+[8T(n)/m]+9 шагов вычислений (поскольку [х]1 < х+1). Так как справедливо limT(n)/n=? n®?, получаем

" d: $ nd Î N: "n³  2: nd: T(n)/n³d (это значит n £, T(n)/d).

Таким образом, для n³2 и n³nd  всегда справедливо n+[n/m]+[8T(n)/m]+9=T(n)[n/T(n)+n/T(n)m+8/m+9/T(n)]£T(n)[1/d+1/md+8/m+9/nd]£ T(n)[8/m+8/d+1/md]

Число d может быть выбрано произвольно. Если мы возьмем d=m+1/8,то имеет место

8/m+8/d+1/md£c.

Это получается из следующего вспомогательного вычисления:

8/m+8/(m+1/8)+1/(mÙ2+1m/8)£24/m£c

Итак, число шагов М^ ограничено числом с*Т(п).

Следствие.

Если LimT(n)/n=?  ,  n>? и c> 0, то справедливо:

DTIME(T(n)) = DTIME(cT(n)) и




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