Vitalik发布新文《Memory access is O(N^[1/3])》：探讨内存访问复杂度与区块链系统效率

10月5日消息，Vitalik 发布新文《Memory access is O(N^(1/3))》探讨内存访问复杂度，讨论了数据结构与算法中的“内存访问”复杂度问题，提出在某些架构或模型下，访问内存的成本可能存在 O(N^(1/3)) 的上界。他指出，经典的排序算法时间复杂度为 O(N log N)，而在考虑内存访问瓶颈时，需要重新审视对大规模数据集的效率分析。 此话题对区块链底层系统设计具有启发意义，尤其是在处理大规模状态、节点同步以及数据可用性（DA / 数据可用性抽样等）机制时，对“读写内存”的效率瓶颈更需谨慎考量。