Skip to content

数组

基本特点

  • 固定大小：数组在创建时需要指定大小（即元素的数量），大小一旦确定就不能更改。这意味着数组的内存空间是连续分配的。

  • 相同类型：数组中的所有元素必须是相同的数据类型，比如整数、浮点数、字符等。

  • 索引访问：数组的元素可以通过索引（下标）直接访问。索引通常从0开始，这使得访问任何一个元素的时间复杂度为O(1)，即常数时间。

  • 内存连续：数组在内存中是连续存储的，这有助于提高访问速度，但也意味着在插入或删除元素时可能需要移动大量数据。

常见操作复杂度

  1. 访问元素 操作：通过索引访问某个元素 时间复杂度：O(1) 解释：数组支持通过索引直接访问元素，访问时间是常数时间，不会随着数组大小变化。
  2. 修改元素 操作：通过索引修改某个元素的值 时间复杂度：O(1) 解释：与访问元素类似，通过索引修改元素值也是常数时间操作。
  3. 查找元素 操作：查找特定值的元素 时间复杂度：O(n) 解释：需要遍历数组中的每个元素进行比较，最坏情况下需要遍历整个数组。如果数组已经排序，则可以使用二分查找，获得O(logn)的复杂度。
  4. 插入元素 操作：在数组中的特定位置插入一个元素 时间复杂度：O(n) 解释：在数组中插入元素时，可能需要移动插入位置后面的所有元素，最坏情况下需要移动n个元素。
  5. 删除元素 操作：删除数组中某个特定位置的元素 时间复杂度：O(n) 解释：删除元素时，可能需要移动删除位置后面的所有元素，以填补空缺，最坏情况下需要移动n个元素。
  6. 追加元素 操作：在数组末尾添加一个元素 时间复杂度：O(1)（如果数组有足够的空间） / O(n)（如果数组需要扩容） 解释：如果数组有足够的预留空间，直接在末尾添加元素是常数时间操作；如果需要扩容（分配新的更大空间并复制原数组元素），则复杂度为O(n)。
  7. 复制数组 操作：创建数组的一个副本 时间复杂度：O(n) 解释：需要遍历原数组并复制每个元素到新数组，复杂度为O(n)。
  8. 数组反转 操作：将数组元素顺序反转 时间复杂度：O(n) 解释：需要遍历一半的数组并交换相应元素的位置，复杂度为O(n)。
  9. 排序 操作：对数组元素进行排序 时间复杂度：O(n log n)（常见高效排序算法） / O(n^2)（简单排序算法） 解释：高效排序算法如快速排序、归并排序的平均复杂度为O(n log n)，而简单排序算法如冒泡排序、选择排序的复杂度为O(n^2)。
  10. 合并两个数组 操作：将两个数组合并成一个 时间复杂度：O(n + m) 解释：假设两个数组的长度分别为n和m，合并操作需要遍历两个数组的所有元素，复杂度为O(n + m)。