爲什麼這個N3數組訪問？

Question

我的算法教科書由羅伯特·塞奇威克和凱文·韋恩說這個for循環有3N數組訪問，和其他地方，我發現了相同的代碼爲這個循環上的一些幻燈片一類聲稱其5N。它看起來像4N，因爲[i]使用了兩次。

這是什麼，爲什麼是它呢？

在算法第三for循環

// 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

鏈接類幻燈片從阿勒格尼學院。 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 [1]被加載兩次，2。 count增加一次，這意味着一個負載和一個商店，+2。 aux是一次寫入，也就是一個商店，+1。

2 + 2 + 1 = 5

我會說這是5N，但平凡可優化通過緩存至4N A [1]中的變量。如果我們將增量作爲單個訪問進行計數，則它可以優化爲3N。 AFAIK，關於增加一個數組的單元是單個訪問還是兩個訪問沒有通用約定。

現代的CPU通常不關心陣列。所有內存均被統一處理。經常（原子）增量操作被提供在內存上工作。我自己會說4N，但可能出於與OP不同的原因。