Виталик публикует новую статью «Доступ к памяти — O(N^[1/3])»: обсуждается сложность доступа к памяти и эффективность блокчейн-системы.

5 октября Виталик опубликовал новую статью под названием «Доступ к памяти — O(N^(1/3)»), в которой исследуется сложность доступа к памяти. В статье обсуждается сложность доступа к памяти в структурах данных и алгоритмах, и предполагается, что в определённых архитектурах или моделях стоимость доступа к памяти может иметь верхнюю границу O(N^(1/3)). Он отметил, что классические алгоритмы сортировки имеют временную сложность O(N log N), и что учёт узких мест, связанных с доступом к памяти, требует переосмысления анализа эффективности больших наборов данных. Эта тема имеет значение для проектирования базовых блокчейн-систем, особенно при работе с большими состояниями, синхронизацией узлов и механизмами доступности данных (например, выборкой DA/доступности данных). Узкое место эффективности «чтение и запись памяти» требует тщательного анализа.