P
скобочную последовательность на правильность за О(1) памяти проверяем? :)
А в чём ошибка, не могу понять. Можете объяснить?
Size: a a a
2020 April 20
CD
А в чём ошибка, не могу понять. Можете объяснить?
Ну константа памяти это регулярные языки. Домашнее задание: доказать, что правильные скобочные последовательности не образуют последнего
ВВ
Ну константа памяти это регулярные языки. Домашнее задание: доказать, что правильные скобочные последовательности не образуют последнего
Единственная переменная-счётчик — это разве не константа памяти?
P
Ну константа памяти это регулярные языки. Домашнее задание: доказать, что правильные скобочные последовательности не образуют последнего
Не совсем понял взаимосвязь.
Есть исходный массив и переменная счётчик. Откуда берётся больше памяти?
Есть исходный массив и переменная счётчик. Откуда берётся больше памяти?
i
Единственная переменная-счётчик — это разве не константа памяти?
Нет
i
Это лошарифм
i
Логарифм
P
Логарифм
А от чего логарифм?
i
От количества обьектов
P
Хм... А каких объектов?
ВВ
Ну константа памяти это регулярные языки. Домашнее задание: доказать, что правильные скобочные последовательности не образуют последнего
«регулярный => константа» — согласен, так как можно построить КА. Но в обратную сторону не обязательно верно, так как могут быть частные случаи, решаемые тоже с константой. Вот, скобочки, например. Обычные, без *. Просто считаем сколько открылось, сколько закрылось. Тут счётчик — это вырожденный стек для одинаковых элементов.
i
Переменная стечкие её размер логарифм
i
Что она считает то?
ВВ
«регулярный => константа» — согласен, так как можно построить КА. Но в обратную сторону не обязательно верно, так как могут быть частные случаи, решаемые тоже с константой. Вот, скобочки, например. Обычные, без *. Просто считаем сколько открылось, сколько закрылось. Тут счётчик — это вырожденный стек для одинаковых элементов.
Так что в принципе, можно считать это решением через автомат с магазинной памятью, только стек тут константу памяти занимает. Такая вот оптимизация.
ВВ
Логарифм
Ну вот счётчик занимает, допустим, 4 байта. От длины строки не зависит. Куда мы ещё память тратим? Кроме исходной строки, конечно, и переменных цикла, которых тоже фиксированное число.
MB
Ну вот счётчик занимает, допустим, 4 байта. От длины строки не зависит. Куда мы ещё память тратим? Кроме исходной строки, конечно, и переменных цикла, которых тоже фиксированное число.
От длины строки он как-раз таки зависит, иначе на строке длины 2**32 упадет
i
Почему 4 байта, тогда уже 1 бит
MB
Кажется, произошло смешение моделей
ВВ
Тогда согласен. Вводим в задачу ограничение на длину строки и будет константа.
ВВ
Кажется, произошло смешение моделей
Именно.