数组

数组是一种基本数据结构，在编程中用于存储相同数据类型的元素集合。这些元素存储在连续内存位置，这允许高效的索引和迭代。数组因其简单性和性能优势而被广泛使用。

数组的关键特性

固定大小（在静态数组中）: 在许多编程语言中，一旦数组被声明，其大小就是固定的，并且在运行时不能更改。这在C和Java等语言中很常见，在这些语言中你需要预先知道数组的大小。
同构元素: 数组中的所有元素都具有相同的数据类型（例如，整数、浮点数、字符），确保了一致的行为和高效的内存分配。
基于索引的访问: 元素可以通过其索引直接访问，允许常数时间访问，表示为 $O(1)$ 。第一个元素的索引是0，第二个的索引是1，依此类推。
连续内存分配: 元素存储在连续的内存位置中，由于更好的缓存利用率而提高了性能。这意味着顺序访问元素会更快，因为它们很可能一起被加载到缓存中。

数组的常见操作

初始化数组

数组可以初始化为空或具有一组指定的初始值。在Python等语言中，列表（功能类似于动态数组）可以使用各种方法进行初始化。

# 初始化一个包含五个元素且都设置为0的列表
arr = [0] * 5  # arr = [0, 0, 0, 0, 0]

# 使用预定义值初始化一个列表
nums = [1, 3, 2, 5, 4]

在C等语言中：

// 使用预定义值初始化一个数组
int nums[] = {1, 3, 2, 5, 4};

// 初始化一个固定大小的数组
int arr[5];  // 元素未初始化

访问元素

访问数组中的任何元素都是一个常数时间操作， $O(1)$ 。元素的内存地址可以使用基地址和元素的索引计算：

$\text{地址} = \text{基地址} + (\text{索引} \times \text{每个元素的大小})$

Python示例：

def random_access(nums):
    import random
    random_index = random.randint(0, len(nums) - 1)
    return nums[random_index]

插入元素

静态数组: 在使用静态数组的语言中，你不能在运行时增加数组的大小。要插入一个元素，你可能需要移动后续元素以腾出空间，这具有 $O(n)$ 的时间复杂度。
动态数组（例如 Python 列表、Java ArrayLists）: 你可以使用内置方法插入元素。然而，在非末尾位置插入需要移动元素，导致时间复杂度为 $O(n)$ 。

def insert(nums, num, index):
    nums.insert(index, num)  # 在指定索引处插入 num
    # 由于元素移动，时间复杂度为 O(n)

删除元素

删除一个元素涉及移动后续元素以填补空缺，这具有 $O(n)$ 的时间复杂度。

def remove(nums, index):
    nums.pop(index)  # 移除指定索引处的元素
    # 由于元素移动，时间复杂度为 O(n)

遍历数组

遍历数组涉及顺序访问每个元素，通常具有 $O(n)$ 的时间复杂度。

def traverse(nums):
    for num in nums:
        print(num)

查找元素

线性搜索: 如果数组是未排序的，你需要执行线性搜索，逐个检查每个元素，这具有 $O(n)$ 的时间复杂度。
二分搜索: 如果数组是已排序的，你可以使用二分搜索通过重复将搜索区间一分为二，在 $O(\log n)$ 时间内查找元素。

def linear_search(nums, target):
    for i, num in enumerate(nums):
        if num == target:
            return i
    return -1

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

扩展数组

静态数组: 由于大小是固定的，扩展需要创建一个更大的新数组并复制元素，这是一个 $O(n)$ 操作。
动态数组: Python等语言会自动处理大小调整。当数组达到其容量时，会分配一个新的更大的数组，并复制元素。这种大小调整操作具有 $O(n)$ 的时间复杂度，但由于摊销，每次插入的平均时间仍为 $O(1)$ 。

def extend(nums, enlarge):
    nums.extend([0] * enlarge)  # 在末尾添加 'enlarge' 个零
    # 时间复杂度为 O(k)，其中 k 是添加的元素数量

优点与缺点

优点

常数时间访问: 直接基于索引的访问允许在 $O(1)$ 时间内检索和修改。
缓存效率: 连续内存分配提高了缓存性能，由于空间局部性加快了数据访问速度。
内存效率: 与链表等更复杂的数据结构相比，数组的开销最小。

缺点

静态数组中的固定大小: 大小必须在编译时已知。如果需要更多空间，你必须创建一个新数组并复制数据，这效率低下。
插入和删除效率低下: 插入或删除元素（末尾除外）需要移动元素，导致时间复杂度为 $O(n)$ 。
内存浪费: 过度估计所需大小会导致未使用的内存分配，而低估则需要重新调整大小，成本很高。

典型应用

数组在各种计算领域中是基础：

数据存储: 对于存储和管理元素类型相同的数据集合至关重要。
算法实现: 用于实现排序（快速排序、归并排序）和搜索（二分搜索）等算法。
科学计算和机器学习: 用于表示向量、矩阵和张量，这些在数值计算中是基础。
系统编程: 用于低级内存管理、硬件接口以及实现堆和哈希表等数据结构。
数据结构: 作为更复杂结构（如栈（后进先出）、队列（先进先出）和动态数组）的构建块。
随机访问和采样: 非常适合需要频繁随机索引访问元素的应用，例如模拟或游戏应用。

数组的关键特性​

数组的常见操作​

初始化数组​

访问元素​

插入元素​

删除元素​

遍历数组​

查找元素​

扩展数组​

优点与缺点​

优点​

缺点​

典型应用​