数据结构与算法 -- 数组

随机访问

数组是一种线性表数据结构,用一组连续的内存空间,来存储一组具有相同类型的数据

线性表

  1. 每个线性表上的数据最多只有两个方向,线性表结构:数组链表队列
  2. 在非线性表中,数据之间并不是简单的前后关系,非线性表结构:二叉树

连续内存 + 相同类型

连续内存 + 相同类型 => 随机访问,但随机访问 ≠ 随机查询
随机访问原理:$a[i]\_address = base\_address + i \times data\_type\_size$,随机访问的时间复杂度为$O(1)$

_

插入 + 删除

  1. 数组为了保持内存数据的连续性,会导致插入操作和删除操作比较低效
  2. 插入操作
    • 假设数组长度为n,将一个数据插入到数组的第K个位置,需要将第k~n的元素都顺序往后挪一位
    • 在数组末尾插入元素,最好时间复杂度$O(1)$;在数组开头插入元素,最坏时间复杂度$O(n)$
    • 假设在每个位置插入元素的概率是一样的,平均时间复杂度为$O(\sum_{i=1}^ni) = O(n)$
    • 如果数组中存储的数据并没有任何规律,数组只是被当做存储数据的集合
      • 可以直接把第k位的元素移到数组的最后,再把新元素直接放到第k个位置,时间复杂度为$O(1)$
  3. 删除操作
    • 与插入数据类似,如果要删除第k个位置的数据,为了保证内存的连续性,也需要挪动数据
    • 删除数组末尾的元素,最好时间复杂度为$O(1)$;删除数组开头的元素,最坏时间复杂度为$O(n)$
    • 假设删除元素的概率是相同的,平均时间复杂度为$O(n)$
    • 在某些场景,可以接受数组中数据的不连续,那可以将多次删除操作集中一起执行,提高删除效率(采用标记删除)
      • 当数组没有更多的空间来存储数据时,再触发一次真正的删除操作,类似于JVM的Mark Sweep

容器 VS 数组

业务开发,直接使用容器即可;底层开发,需要将性能做到极致,首选数组

下标从0开始

  1. 下标的确切含义:偏移
  2. 历史原因,C语言从0开始计数
0%