비탈릭이 새로운 글을 발표하며 "메모리 접근은 O(1)"이라는 가정을 의문시했다

ChainCatcher 메시지, 10월 5일, 이더리움 공동 창립자 비탈릭 부테린이 최신 기사 《Memory access is O(N\^(1/3))》를 발표하여 메모리 접근 복잡도를 탐구하고 데이터 구조 및 알고리즘에서의 "메모리 접근" 복잡도 문제를 논의했습니다.

문중에서 제안된 바에 따르면, 일반적으로 산술 연산(덧셈, 곱셈, 나눗셈…)은 고정 크기의 숫자에 대해 하나의 시간 단위가 필요하다고 여겨지며, 메모리 접근도 하나의 시간 단위가 필요하다고 여겨지지만, 이러한 주장은 정확하지 않습니다. 이론적으로나 실제로 메모리 접근은 O(N\^⅓)의 시간이 필요합니다: 만약 당신의 메모리가 8배 크다면, 이를 읽고 쓰는 데 필요한 시간은 2배 증가할 것입니다.
비탈릭은 이 규칙이 암호학 및 알고리즘 최적화에 실제적인 영향을 미친다고 지적하며, 미래의 계산 모델이 메모리 계층 및 물리적 제한을 더 현실적으로 반영해야 한다고 촉구했습니다.