数据结构和算法
2020-06-10 本文已影响0人
Zorin
1. 代码运行效率
复杂度
复杂度通常包括 时间复杂度 和 空间复杂度
复杂度的表示方法 O(n) O(2n) O(n²) O(log n);
在具体算法复杂度时需要注意：
- 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度
- 复杂度相加的时候，选择高者作为结果，也就是 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度
- O(1)也是表示一个特殊复杂度，即任务与算例个数无关
时间复杂度与代码的结构设计高度相关
空间复杂度与代码中数据结构的选择高度相关
降低时间复杂度的方法
算法： 递归，二分法，排序算法，动态规划
降低空间复杂度的方法
数据结构
复杂度降低的核心方法论
降低复杂度的方法的三个步骤：
- 暴力解法：在没有任何时间，空间约束下，完成代码任务的开发
- 无效操作处理：将代码中的无效计算，无效存储剔除，降低时间或空间复杂度
- 空间转移：设计何时数据结构，完成时间复杂度向空间复杂度的转移
4. 如何完成线性表结构下的增删查
线性表的原理，线性表对于数据的增删查操作
线性表结构的每个节点，由数据的数值和指向下一个元素的指针构成
据结构组合方式的不同，除了单向链表以外，还有双向链表，循环链表以及双向循环链表等变形
- 链表在增，删方面比较容易实现，可以在 O(1)的时间复杂度内完成
- 对于查找，需要对全部数据进行遍历
线性表 的价值在于
- 它对数据的存储方式是按照顺序的存储
- 当数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适
- 链表的翻转，快慢指针的方法，是必须掌握的内容
- 存储空间不一定是连续的
数组(顺序) 的价值在于
- 数组在连续的空间进行存储，可以直接求解出数组的长度
- 数组可以通过索引值去查找元素，然后对相应的数据进行交换操作而完成翻转
5. 栈：后进先出的线性表，如何实现增删查
线性表 对数据的顺序非常敏感，而且它对数据的增删操作非常灵活
在有序排列的数据中，可以灵活的执行增删操作
它的灵活性在某种程度上破坏了数据的原始顺序
在某些需要严格遵守数据处理顺序的场景下，就需要对线性表予以限制
- 限制后的线性表--
顺序栈
链栈
6. 队列：先进先出的线性表，如何实现增删查road
队列具有先进先出的特点
在面对数据处理顺序非常敏感的问题时，队列是个不错的选择
-
定义
- 顺序队列：内存空间顺序存储
- 链式队列：链式结构存储
-
时间复杂度
- 循环队列和链式队列的新增、删除操作都为O(1)
- 在查找操作中，队列只能通过全局遍历的方式进行，需要O(n)的时间复杂度
-
空间性能方面
- 循环队列必须有一个固定的长度，因此存在存储元素数量和空间的浪费问题
- 链式队列更为灵活一些
-
技术选型
- 在可以确定队列长度最大值时，建议使用循环队列
- 无法确定队列长度时，应考虑使用链式队列
