数组

在本课程章节中，我们将探讨各种数据结构，并理解如何分析它们上不同操作的时间复杂度。我们还将延伸讨论空间与时间之间的权衡关系，以帮助读者建立关于复杂度分析的思维方式。

我们将从最基本的数据结构开始——数组。几乎所有编程语言都支持用户创建数组。众所周知，对数组的插入或访问操作都是常数时间操作，即 O(1)。但为什么这些操作能在常数时间内完成呢？

关键在于连续的内存分配。只要知道元素的索引，数组就能通过连续内存布局实现常数时间的访问或插入。无论你使用何种语言平台，当你创建一个数组时，该平台都会向底层操作系统申请一块连续的内存空间。假设操作系统为一个包含 10 个元素的数组分配了如下内存块：

操作系统所分配的内存块

假设我们前面请求的数组是用于存储整数类型。接下来要考虑的是我们所请求数组的类型大小。这里的“类型”指的是数组中存储的数据类型，可能是整数、字符，甚至是对象。以 Java 为例，一个整数占 4 个字节，我们就以此为例。需要注意的是，只要知道了数组在内存中的起始地址，就可以很容易地根据元素的索引计算出该元素在内存中的起始地址。

举个例子，假设下面这段代码中数组的起始地址是 25：

1 // 初始化一个包含10个元素的数组
2 // 变量 myArray 指向内存地址 25
3 int[] myArray = new int[10];

变量 myArray 实际上指向计算机内存中的地址 25。同时我们知道每个整数占 4 个字节。第一个整数位于地址 25，第二个整数位于 25 + (1 * 4) = 29，第三个整数位于 25 + (2 * 4) = 33。要找出数组中第 n 个元素在内存中的位置，可以使用以下通用公式：

$第n个数组元素的地址 = 数组起始地址 + (n \times 类型大小)$

对于我们的示例数组，该公式变为：

$A[n] = 数组起始地址 + (n \times 4)$

最后需要理解的是：访问数组任意元素仅需一次数学计算。试想一下，无论数组大小是 10、100 还是 100 万，计算任意元素地址所需的步骤数量会改变吗？不会。数组的大小并不影响我们计算某个元素地址的方式。一旦算出地址，操作系统和底层硬件将协同工作，从物理内存中取出对应数组元素的值。

无论我们是获取第一个元素还是第一百万个元素的地址，这个数学计算所需的时间始终相同。因此，数组的访问或读取操作是常数时间操作，即 O(1)。访问数组的最后一个元素或中间元素，在计算内存地址时所需的步骤数是一样的。

其他考虑因素

细心的读者可能会注意到，数组要求我们预先预留一块连续的内存空间。如果数组大部分位置未被使用（稀疏），就会造成大量空间浪费。这是一种典型的空间换时间的权衡：我们牺牲了存储空间，换取了更快的访问速度。虽然插入和访问操作变得高效（O(1)），但可能伴随着较大的空间开销。

脚本语言中的细节

有 JavaScript 或其他类似语言经验的开发者可能会疑惑：如果这些语言在初始化数组时无需声明大小，上述原理是否仍然适用？答案是肯定的。实际上，这类语言背后的数组仍然是固定大小的。当用户尝试向已满的数组添加新元素时，运行平台会创建一个新的、容量更大的数组，并将原数组中的所有元素复制过去。这一过程对开发者透明。这种能自动扩容的数组被称为动态数组，我们将在后续章节中详细讨论。