数组(Array)是一种线性表数据结构
。它用一组连续的内存空间
,来存储一组具有相同类型的数据
。
一维数组的寻址公式:
a[i]_address = base_address + i * data_type_size
对于 m * n 的二维数组,a [ i ][ j ] (i < m,j < n)的寻址公式:
a[i][j]_address = base_address + ( i * n + j) * data_type_size
数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。
(不是所有的查询的时间复杂度都是O(1),只有根据下标访问才是)
参考:
极客时间:《数据结构与算法》王争