arrays - 为什么访问这个 N3 数组？

Question

我的由 Robert Sedgewick 和 Kevin Wayne 合着的算法教科书说这个 for 循环有 3N 数组访问，而在其他地方我在一些声称有 5N 的类的幻灯片上找到了这个循环的相同代码。对我来说它看起来像 4N，因为 a[i] 使用了两次。

这是什么，为什么会这样？

算法中的第三个for循环

// Distribute the records.
for (int i = 0; i < N; i++)
  aux[count[a[i].key()]++] = a[i];

链接到 sedgewick 的文章。 http://www.informit.com/articles/article.aspx?p=2180073

链接到阿勒格尼学院的类幻灯片。 http://cs.allegheny.edu/sites/jwenskovitch/teaching/CMPSC250/docs/lectures/14%20String%20Sorts.pdf

链接到过去的堆栈溢出。 What constitutes 'array access' in the context of algorithms?

Answer 1

a[i] 被加载了两次，+2。count[...] 递增一次，表示一次加载一次存储，+2。aux[...] 写一次，表示一个store，+1。

2+2+1=5

我会说它是 5N，但通过在变量中缓存 a[i] 可以简单地优化到 4N。如果我们将增量计为单次访问，​​则可以从 4N 优化到 3N。据我所知，关于递增数组的单元格是单次访问还是两次访问，没有通用的约定。

现代 CPU 通常不关心数组。所有内存都被统一处理。经常(原子)增量操作提供对内存的工作。我自己会说 4N，但可能出于与 OP 不同的原因。