AK
Это занудство из разряда, на самом деле не константная память, а O(logN)
Size: a a a
2021 May 23
NE
смотрю алгоритм и что-то не пойму где там logN, там же постоянное число индексов, нет?
NE
подумал, если вы про то что для хранения числа представляющего индекс нужно logn бит, то это реально занудство, программа все равно не сможет хранить строку длиной больше чем лезет в машинное слово
CD
Разница всего лишь в класс грамматики, да
CD
а еще программа не может использовать больше, чем 2^машинное_слово памяти, поэтому алгоритм со стеком работает за О(1)
AT
для хранения N чисел из
{1, ..., M} нужно N log M памяти?)NE
это так не работает
CD
как раз так и работает, вы только что объявили N <= 2^длина_машинного_слова = const
MB
Ну, зависит от модели
MB
Кажется, довольно полезно рассматривать модель, в которой в каждой ячейке хранится число, не превосходящее полином от размера инпута и потребления памяти
NE
когда это становится не const компьютер перестает работать
MB
В такой модели индекс всегда влезает в одну ячейку, и потребление памяти будет O(N).
CD
когда N <= const асимптотические обозначения перестают работать
AT
когда перейдём к аналоговым компьютерам и в одном флоате будет лежать реальный real number, то придётся делать оговорки)
MB
Ну там кажется надо ввести полиномиальное ограничение на само значение и полиномиальное ограничение на точность
CD
Ну ты же понимаешь, что абсурдно утверждать, что константный объем памяти может иметь бесконечное число возможных состояний? Понятно, что арифметическую поправку обычно дропают
NE
MB
> константный объем памяти может иметь бесконечное число возможных состояний
Внутренних противоречий тут никаких не возникает, а к реальности такая модель ближе.
Внутренних противоречий тут никаких не возникает, а к реальности такая модель ближе.
CD
Ну... тебе будет сложно автоматные и КС грамматики различать :)
MB
Ну и тут наверное можно развести философию про семейство машин, где k-тая хранит k-битные числа и содержит 2^k памяти