66
数据结构与算法: 数组
source link: http://debugtalk.com/post/data-structure-algorithm-array/?amp%3Butm_medium=referral
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组有两个最大的特点：
- 线性表数据结构 ：线性表（Linear List）就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组，链表、队列、栈 都是线性表结构。与之对应的是非线性表数据结构，如二叉树、堆、图等。
- 连续的内存空间和相同类型的数据 。
线性表 vs. 非线性表
复杂度分析
数组具有如下特性：
- 非常高效的“随机访问”：通过下标访问只需一次操作即可获取到数据
- 低效的“插入”和“删除”：插入和删除后，需要同时移动数组中的其它数据
对应的时间复杂度如下：
- Access: O(1)
- Insert: 最小 O(1)，最大 O(n)，平均 O(n)
- Delete: 最小 O(1)，最大 O(n)，平均 O(n)
注意：数组的查询操作并非为 O(1)，即便是排好序的数组，采用二分查找，时间复杂度也是 O(logn)。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK