隨機存取數組的時間複雜度

Question

當分析算法的時間複雜度時，我們通常認爲數組的隨機存取時間是一個常數（數組的大小n不是常數），但是爲什麼？

考慮圖靈機模型，其中一個數組存儲在磁帶中，以訪問數組的特定元素，其磁帶頭必須移動到該位置，這需要O（n）時間。還是有任何其他方法來存儲數組的圖靈機，以便隨機訪問只需要一段時間？

Answer 1

戈登put it quite excellently：

計算機不圖靈機。在「真正的」典型通用機

數組不存儲在「無限長」線性存儲，但在RAM，隨機存取存儲器。從技術上講，（並且很坦率地簡化了很多），你只需從RAM中獲取任何地址，將其理解爲通過內存地址的路徑。因此訪問任何地址需要相同的時間。

現在，對於數組，您可以通過取第一個元素的地址並添加n倍單個元素的大小來直接計算第n個元素的地址。

記住：圖靈機是如何證明和理解某些事情，而不反映事物實際上是如何做現實概念。複雜性計算也是如此：當然，實際上訪問矢量中的任何元素並不總是完全相同，因爲計算機科學人員需要做出的有關算法的有趣事情的假設並不總能完全表示每一臺能夠運行給定算法的物理機器 - 真正的現代計算機都具有緩存和預取內存控制器，因此訪問你剛剛訪問的一塊內存比獲取內存要快得多。

Answer 2

由於內存模型（cpu寄存器，RAM和外部存儲器），算法的分析不考慮開銷。

原因很簡單，它會使分析不通用。那麼分析將取決於您使用的是哪種硬件。這會使分析變得複雜，並且對於通用目的來說它不會有用。

Answer 3

數組訪問是恆定時間的，因爲數組元素是連續存儲的。與鏈接列表訪問進行對比。在鏈表中，每個節點都具有到下一個節點的地址。這迫使CPU去所有的n-1節點到達第n個節點。但是對於數組，您直接知道地址：address_to_first_element + (n-1)*size_of_elements，因此可以在恆定時間訪問該元素。 這裏的假設是數據存儲在隨機訪問內存。

對於圖靈機，數據存儲在磁帶上。磁帶是一種線性訪問設備。該Wikipedia article差不多說：

雖然他們可以表達任意計算，其簡約 的設計使得它們不適合在實際計算：實際 電腦都基於不同的設計，不像圖靈機， 使用隨機訪問記憶。

Answer 4

在一個數組中，所有元素都存儲在一個連續的內存位置。因此，要訪問任何元素，元素的地址計算爲與數組基地址的偏移量，並且需要一個乘法來計算應該被添加到基地址以獲取元素的內存地址。 所以，首先計算該數據類型的元素的大小，然後將其乘以元素的索引以獲取要添加到基地址的值。由於該過程需要一次乘法和一次加法，因此可以在常量時間內訪問數組元素。