i
Для любой ограниченной задачи достаточно констант ной памяти
Size: a a a
2020 April 20
P
Ааа. Ну если действительно считать, что длина строки неограниченна, то все объяснения становится понятными.
ВВ
Такие оценки на практике не очень интересны. Потому и есть разные модели.
EZ
Тогда согласен. Вводим в задачу ограничение на длину строки и будет константа.
вводишь в любую задачу ограничение на длину ввода и будет константа
EZ
а так как размер ввода ограничен количеством планковых объемов во вселенной, то любая задача решается за константу
EZ
профит
ВВ
вводишь в любую задачу ограничение на длину ввода и будет константа
Да, я понимаю.
i
А так задача решается просто. Пусть длина цепочки 10. Генерируещь правильные случайные цепочки длины 10 в степени 2 умножить на три раз. Если ни разу не получил исходную ответ она неправильная
MB
А так задача решается просто. Пусть длина цепочки 10. Генерируещь правильные случайные цепочки длины 10 в степени 2 умножить на три раз. Если ни разу не получил исходную ответ она неправильная
О_о
i
Так это с вероятнистниками
CD
Единственная переменная-счётчик — это разве не константа памяти?
нет, если она считает до бесконечности
ВВ
нет, если она считает до бесконечности
Обсудили уже. Мы о разных cost models говорили. Так-то константной памяти и для регулярных языков не хватит, если обходить строку с доступом к символам по индексу.
CD
Обсудили уже. Мы о разных cost models говорили. Так-то константной памяти и для регулярных языков не хватит, если обходить строку с доступом к символам по индексу.
ошибка в вашей модели строки в голове
CD
вы почему-то считаете её массивом
ВВ
вы почему-то считаете её массивом
Я практик. :)
CD
Я практик. :)
у которого память случайного доступа за 1? :)
MB
Так это с вероятнистниками
зачем рандомизированный алгоритм если есть детерминированный?
Это что, какая-то шутка, для которой я не секу в метаиронии?
Это что, какая-то шутка, для которой я не секу в метаиронии?
i
так бывает на машине тьюринга со смышленным оракулом
ВВ
у которого память случайного доступа за 1? :)
Если в кэш влезла.
CD
Если в кэш влезла.
в L1 заранее