极简教程:数据结构与算法(二)
发布于 5 年前 作者 shixinglong007 4443 次浏览 来自 分享

这是一套关于数据结构与算法的系列文章,值得你持续关注

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. 数组,插入优化

如果不需要排序,那么不用每次都对插入位置后的元素做位移。可以尝试替换法

demo_006_1.png

7. 删除优化

不用每次删除都 给元素移位,可以先标记被删除的元素。等删除的元素积累一段之后一并删除。

demo_006_2.png

8. 大部分语言都有对数组做扩张,比如 javascript 中 Array。其实 javascript 中没有严格意义上的数组。

9. 开发时一般都用 arrayList,如果初始化时给设定一个长度,那么可以起到优化的作用。减少一部分 O(n) 操作

10. 在数据长度固定的情况下,建议使用数组。这样执行效率更高。

如有不足,欢迎补充。 公众号.png

回到顶部