重访内存访问：O(N^⅓)复杂性争论
realtime news Oct 04, 2025 20:12
Vitalik Buterin讨论了内存访问的复杂性，通过提出一个O(N^⅓)模型来挑战传统观点。这对算法优化和硬件设计具有影响。
在对计算效率的发人深省的探索中，Vitalik Buterin提出了有关内存访问复杂性的传统理解的问题。在最近的一篇博客文章中，Buterin认为内存访问的时间复杂性应被视为O(N^⅓)，而不是通常假设的O(1)。这一范式转变可能对优化算法和设计硬件系统产生重要影响。
O(N^⅓)的理论基础
Buterin基于数据检索的物理限制提出了他的论点。他指出，光速限制了处理器访问内存的能力，访问时间与距离成比例增加。这导致了内存大小和访问时间之间的立方关系，其中内存大小增加八倍会使访问时间增加一倍。该理论模型表明，内存访问时间随着内存大小的立方根增长。
经验观察
Buterin的理论得到了不同类型内存（如寄存器、缓存和RAM）的经验数据支持。他指出，将访问时间视为内存量的立方根提供了惊人准确的估计。然而，考虑带宽时，由于架构差异，特别是在缓存和DRAM中，相关性不那么精确。
实际影响
该模型在密码学等领域具有重要意义，其中优化算法通常依赖于预计算表。Buterin指出，这些表的大小应仔细考虑，因为如果超出缓存容量，较大的表可能导致更慢的访问时间。他讲述了自己的二进制域计算经验，其中一个8位预计算表由于更快的缓存访问而优于16位表。
未来方向
随着通用CPU极限的接近，Buterin建议理解内存访问复杂性对于开发高效的ASIC和GPU将是至关重要的。可以分解为本地化计算的任务将受益于O(1)访问时间，而那些有大量内存相互依赖的任务可能面临O(N^⅓)的限制。
Buterin的这一探索邀请进一步研究能够更好地捕捉内存访问细微差别的数学模型，可能会推动软件优化和硬件架构的进步。
更多详细信息，请访问Vitalik Buterin在vitalik.eth.limo上的原始文章。
Image source: Shutterstock.jpg)