极简教程:数据结构与算法(二)
这是一套关于数据结构与算法的系列文章,值得你持续关注
2020-4-29
数组篇
我尽量用 最少的文字,最少的代码。来讲明白数据结构与算法。
1. 数组是“线性数据结构”,同样的数据结构还有“链表”,“栈”,“队列”
2. 与之对立的概念是 “非线性表” 。二叉树,堆,图等。因为这些数据结构的方向不只是“前”,“后”。
3. 数组的原理:在内存地址中找到开始的位置,划定一片连续的内存地址。只存储相同类型的数据,这样方便寻址。
4. 因为是连续的内存地址,所以才能实现随机访问元素
寻址算法
a[i] = 数组开始的位置 + i * 固定大小
5. 数组复杂度分析
动作 | 复杂度 |
---|---|
array 增 | O(n) |
array 删 | O(n) |
array 改 | O(1) |
array 查:根据下标 | O(1) |
array 查:循环查 | O(logn) |
6. 数组,插入优化
如果不需要排序,那么不用每次都对插入位置后的元素做位移。可以尝试替换法
7. 删除优化
不用每次删除都 给元素移位,可以先标记被删除的元素。等删除的元素积累一段之后一并删除。
8. 大部分语言都有对数组做扩张,比如 javascript 中 Array。其实 javascript 中没有严格意义上的数组。
9. 开发时一般都用 arrayList,如果初始化时给设定一个长度,那么可以起到优化的作用。减少一部分 O(n) 操作
10. 在数据长度固定的情况下,建议使用数组。这样执行效率更高。
如有不足,欢迎补充。