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

       

Ленточная сложность


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

Рассмотрим Т-машину М с одной входной лентой, на которую нельзя записывать какую-либо новую информацию и которая содержит маркер конца, и с k односторонне-бесконечными лентами. Пусть при обработке принимаемого слова w длины n (обработка которого завершается «Остановкой машины) машина М использует bi(w) ячеек памяти на ее i-й  ленте (1? i ?k).



Содержание раздела