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