大数组中如何以Θ(1)时间访问索引999,999,999的元素？

嘿，这个问题问到点子上了——很多刚接触数据结构的人都会有这个疑惑，我来给你掰扯明白：

核心原因：数组的连续内存布局 #

数组在计算机内存里是连续分配的一块存储空间，而且每个元素的大小是固定的（比如int类型通常占4字节，double占8字节）。当你创建数组时，系统会记录它的「基地址」（也就是第一个元素的内存地址）。

访问任意索引的本质：直接地址计算 #

访问索引为i的元素时，计算机根本不需要从第一个元素开始循环计数到i，而是直接用公式算出目标元素的内存地址：

目标地址 = 数组基地址 + i * 单个元素字节数

举个实际例子：假设数组基地址是0x1000，每个元素占4字节，那索引999,999,999的元素地址就是 0x1000 + 999999999 * 4。这个计算是固定步数的算术运算，不管i是0还是10亿，计算时间都完全一致，所以时间复杂度是Θ(1)。

为什么你会误以为有循环？ #

你可能把数组和链表搞混了：链表的元素是分散存储的，每个元素只存下一个元素的地址，所以访问第n个元素必须从表头开始逐个遍历，时间复杂度是Θ(n)。但数组完全不一样，它的随机访问特性就是依赖这种直接的地址计算，没有任何循环操作。

总结 #

不管数组有多大（哪怕是10亿个元素），访问任意索引的元素都是一步到位的直接计算，不存在计数循环，所以时间复杂度肯定是Θ(1)。

内容的提问来源于stack exchange，提问作者shir k