Новая статья Виталика: Традиционное представление о том, что "доступ к памяти имеет сложность O(1)" не является точным

PANews сообщил 5 октября, что соучредитель Ethereum Виталик Бутерин опубликовал новую статью под названием "Memory Access is O(N^(1/3))." В статье утверждается, что распространенное предположение о том, что арифметические операции (сложение, умножение, деление и т.д.) для чисел фиксированного размера занимают одну единицу времени, и что доступ к памяти также занимает одну единицу времени, неточно. Как в теории, так и на практике, доступ к памяти занимает время O(N^⅓): если ваша память в восемь раз больше, то время, необходимое для чтения и записи, увеличится в два раза. Виталик отметил, что этот принцип имеет практические последствия для криптографии и оптимизации алгоритмов, и призвал к тому, чтобы будущие вычислительные модели более реалистично отражали иерархии памяти и физические ограничения.