Обсуждение:Временная и пространственная сложность алгоритмов/Задачи/ex-braces-parse-in-logspace/c000076 — различия между версиями
Материал из DISCOPAL
(Полностью удалено содержимое страницы) |
|||
Строка 1: | Строка 1: | ||
− | + | [[Category:На проверку]] | |
+ | Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace. |
Версия 08:39, 7 мая 2015
Скобочная последовательность правильная, если: число ) = числу (, не существует ситуации, что число ) больше числа ( если идти от начала слова. На двух-ленточной МТ алгоритм, считающий количество ( и ) и разность между ними на каждом шаге занимает 3 дополнительных ячейки на ленте, значит принадлежит logspace.