将数组初始化为 0 需要多长时间？

Question

我很困惑是否
int arr[n]={0}需要恒定的时间，即 O(1) 还是 O(n)？

Answer 1

您应该期望 O(N) 时间，但有一些警告：

• 如果数组占用的内存小于字大小，则为 O(1)。（它可能是 O(1) 一直到现代 CPU 上的缓存行大小）
• 如果数组适合内存中的单个层，则为 O(N)。
• 如果数组通过层推送则很复杂：所有现代计算机上都有多个层（寄存器、L0 缓存、L1 缓存、L3 缓存？、多 CPU 机器上的 NUMA、虚拟内存（映射到交换），...） . 如果数组不能放在一个数组中 - 将会有严重的性能损失。

CPU 缓存体系结构会严重影响将内存清零所需的时间。实际上，将其称为 O(N) 有点误导，因为如果它落在缓存边界（行或整个）上，从 100 到 101 可能会将时间增加 10 倍。如果涉及交换，情况可能会更加戏剧化。当心分层内存模型...