Vitalik 發佈新文，質疑“記憶體存取是O(1)”的假設

ChainCatcher 消息，10 月 5 日，以太坊聯創 Vitalik Buterin 發佈最新文章《Memory access is O(N\^(1/3))》探討內存訪問複雜度，討論了數據結構與算法中的"內存訪問"複雜度問題。

文中提出，通常算術運算（加法、乘法、除法……）對於固定大小的數字被認為需要一個時間單位，內存訪問也被認為需要一個時間單位，這種說法並不準確。無論在理論上還是在實踐中，內存訪問都需要 O(N\^⅓) 的時間：如果你的內存是其 8 倍大，那麼對其進行讀寫操作所需的時間將增加 2 倍。
Vitalik 指出這一規律在密碼學及算法優化中具有實際影響，並呼籲未來計算模型應更真實地反映內存層級與物理限制。