c - 将数组初始化为 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 倍。如果涉及交换，情况可能会更加戏剧化。当心分层内存模型...