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

Question

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

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

Answer 1

戈登说得非常好：

计算机不是图灵机。

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

现在，对于数组，您可以通过获取第一个元素的地址并添加单个元素大小的 n 倍来直接计算第 n 个元素的地址。

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