the myth of RAM, and of O(n), and of NNO

Краткое содержание: С учётом того, что в современных компьютерах имеется несколько уровней кэша, а на расстоянии N см от процессора может располагаться максимум k*N*N байт памяти, следует считать, что время доступа к произвольной ячейке памяти пропорционально квадратному корню от общего количества используемой при работе алгоритма памяти.
Но советую всё-таки прочитать статью полностью.

Оригинал взят у juan_gandhi в the myth of RAM, and of O(n), and of NNO

http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i

see also http://philosophy.stackexchange.com/questions/37665/are-there-simpler-kinds-of-arithmetic-that-are-decidable

and I wonder when we start using linear logic IRL