为什么这个N3数组访问？

Question

我的算法教科书由Robert和Kevin编写，它说这个for循环有3N数组访问，在其他地方，我在一个声称5N的类的幻灯片上找到了这个循环的相同代码。在我看来像是4N，因为人工智能被使用了两次。

是什么?为什么是这样？

第三循环在算法中

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

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

链接到allegheny学院的课堂幻灯片。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

ai装了两次，+2.数.增加一次，这意味着加载和存储，+2.aux.写一次，意思是存储，+1。

2+2+1=5

我会说它是5N，但是可以通过在变量中缓存ai来优化到4N。如果将增量计算为单个访问，则4N可优化为3N。AFAIK，对于递增数组的单元格是一次访问还是两次访问，没有通用的约定。

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