Vitalikが新しい文を発表し、「メモリアクセスはO(1)である」という仮定に疑問を呈しました。

ChainCatcher のメッセージ、10 月 5 日、イーサリアムの共同創設者 Vitalik Buterin が最新の記事「Memory access is O(N\^(1/3))」を発表し、メモリアクセスの複雑さについて探討し、データ構造とアルゴリズムにおける「メモリアクセス」の複雑さの問題を議論しました。

文中では、通常の算術演算（加算、乗算、除算……）は固定サイズの数字に対して1つの時間単位を必要とすると考えられていますが、メモリアクセスも1つの時間単位を必要とするという考え方は正確ではないと述べています。理論的にも実践的にも、メモリアクセスには O(N\^⅓) の時間が必要です：もしあなたのメモリが8倍の大きさであれば、その読み書き操作に必要な時間は2倍に増加します。
Vitalik はこの法則が暗号学やアルゴリズムの最適化に実際の影響を持つことを指摘し、将来の計算モデルはメモリ階層と物理的制約をより真実に反映すべきだと呼びかけました。