一个知乎问题 数组的 O(1) 时间复杂度之所以高效是因为内存连续性吗？

先直接回答问题，我后面会补充知识背景，学术到工程的视角都讲一讲，尽量全面。

数组的 $O(1)$ 时间复杂度之所以高效是因为内存连续性吗?

数组的 $O(1)$ 时间复杂度在访问第 1 个元素和访问第 1 万个元素时都是同样的时间，这里面的主要原因是数据的内存空间连续。

在这个基础上操作系统可以快速的根据固定的公式来算出要获取的元素的内存地址，在计算机组成原理层面也是这样的，根据基地址快速算出要查找的数据的偏移量就可以算出来。

而链表这种结构它的内存空间不一定连续，内存分布是无规律的所以无法根据公式来快速寻址某个数据的内存地址。

这样的理解是否准确？你有什么要补充的观点吗？

当你和链表对比，确实可以这么说。

但是根本原因其实是两点：高效的指针算术，高效的随机访存。指针算术是将指针和整数加减，或者两个指针相减。随机访存就是拿一个地址去读写内存对应位置的值。

时间复杂度 $O(1)$ 是指内存或 cpu 内部的寄存器的指令周期为 1 次，这个涉及到计算机组成原理的知识点，各位大侠有何指教？

访问内存不只有 1 个时钟周期，读写内存需要几十到几百个，读写最快的 cache（L1 cache）也要 3-4 个。cpu 内部的寄存器的指令周期，如果题主是指读写寄存器，那确实是 1 个周期。

但是，问题是时间复杂度的定义不依赖现实的硬件。时间复杂度是先定义了一个基础指令集（比如上面的指针算术、随机访存等），然后算法需要的指令数，相比于输入规模的增长趋势即是时间复杂度。

其实我觉得系统性学习某个科目是有点不太现实的，但是零散的学习又感觉缺少点什么。

各位有何高见？

坚持看一本书，每天看一点，为什么会不现实。要我说肯定推荐系统性学习。

---

这个数组的 $O(1)$ 随机访存是个不错的话题，既然写回答了，我就从学术到工程的视角展开讲讲。

1. 学术视角

首先如前文所说，时间复杂度是先定义了一个基础指令集，然后算法需要的指令数，相比于输入规模的增长趋势即是时间复杂度。

增长趋势也需要定义。令输入规模为 $n$（比如输入是 $n$ 个字符，或者比特等），算法需要 $T(n)$ 个指令数，如果函数 $f$ 和一个常数 c 满足任意 n 都有 $T(n)\le c f(n)$，那么 $T(n)=O(f(n))$。这里只定义大 O 了，剩下的可以自行学习。

那么基础指令集是怎么来？答案是：随意，喜欢什么用什么。话虽如此，做研究时一般还是会选个常用的，这样才有研究价值。所以，常用计算模型该端上来了。

1.1. 图灵机

图灵机虽然很弱，但它太有名了，不得不提一下。

众所周知，图灵机由无限长纸带、读写头和状态寄存器组成，纸带上是离散的存储单元，存储有限字符集里的一个字符。

但是图灵机并不适合作为大多数算法的模型，它和现实机器差太远了。指定一个地址读取元素，就是随机访存，图灵机需要 $O(n)$ 时间复杂度（把读写头移过去）。

1.2. RAM (Random Access Machine) 模型

为了解决图灵机的痛点，RAM 模型的做法很直接。RAM 引入了一个内存，允许常数时间完成随机访存。同时，每个存储单元可以存放任意整数。

RAM 有指针算术和随机访存的能力，因此它可以做到 $O(1)$ 的数组随机访存。

RAM 的一个变体 Word RAM 模型，是算法分析里最常用的模型。具体和主题不是很相关，就不详细展开了。

1.3. 指针机 (Pointer Machine) 模型

指针机是一个弱一点的模型，它可以随机访存（这可能有点不严谨），但是禁止指针算术，而且直接禁止了数组。

禁止指针算术同样导致无法 $O(1)$ 访问数组了（虽然数组也被禁了）。如果我们要模拟出数组的效果，就只能用平衡树或其他结构来实现 $O(\log n)$ 的数组随机访存。

1.4. 生命游戏

甚至，我们可以用生命游戏来研究算法。这里的随机访存是 $O(\sqrt n)$，n 是世界的单元数。

这是因为生命游戏有“光速”的限制，就是信息传递的最快速度。

2. 工程视角

细思极恐，我们的世界不也有光速吗。

我们定义时间复杂度时，有一个“任意 $n$”的说法，这其实涉及到无穷大。可以这么说，任何现实的东西碰到无穷大，都会粉身碎骨。

访问内存复杂度是 $O(1)$，这没问题。但内存也就上百 GB，就算用 NUMA 架构，也就几个 TB。可是算法的规模是任意大的。

于是我们向 device io 寻求帮助，把数据放入硬盘，或者用高性能网络将多个机器连起来。我们的容量到达了 PB 级别。可是，算法的规模是任意大的。

于是我们向互联网寻求帮助，在这一层，碰到光速的限制。

事实上，从内存和 NUMA，到 device io，规模越大延迟越大。$O(1)$ 的时间复杂度注定只是理想。

---

所以工程上为什么能说数组 $O(1)$ 复杂度呢？其实也是因为现实。如果讨论现实问题时，不需要超出内存容量的数组，那就能认为数组的复杂度是 $O(1)$。这是对问题的合理简化。

学术上创造了现实不存在的 RAM 模型，工程上是对问题的简化。不管是哪边都能得出数组的复杂度是 $O(1)$，算是殊途同归了。