arrays - 随机访问数组的时间复杂度

Question

在分析一个算法的时间复杂度时，我们通常认为随机访问一个数组的时间是一个常数(数组的大小n不是一个常数)，但为什么呢？

考虑图灵机模型，其中数组存储在磁带中，要访问数组的特定元素，其磁带头必须移动到该位置，这需要 O(n) 时间。或者是否有任何其他方法可以为图灵机存储数组，以便随机访问只需要常数时间？

Answer 1

戈登 put it quite excellently :

Computers are not Turing machines.

“真正的”典型通用机器上的数组并不存储在“无限长”的线性存储器中，而是存储在 RAM 中，随机存取存储器。从技术上讲，(坦率地说，简化了很多)，您只需将 RAM 理解为通过内存地址的路径即可从 RAM 获取任何地址。因此访问任何地址都需要相同的时间。

现在，对于数组，您可以直接计算第 n 个元素的地址，方法是将第一个元素的地址加上单个元素大小的 n 倍。

请记住:图灵机是关于如何证明和理解某些事物的概念，并不反射(reflect)事物实际完成的方式。复杂性计算也是如此:当然，在现实中访问向量中的任何元素并不总是需要完全相同的时间，因为计算机科学人员需要做出的关于算法的有趣事情的假设并不总是完全代表每台可以运行给定算法的物理机器——真正的现代计算机都有缓存和预取内存 Controller ，因此访问你“刚刚”访问过的一 block 内存比仅仅获取任何内存要快得多。