数据结构和算法

1. 代码运行效率

复杂度

复杂度通常包括 时间复杂度 和 空间复杂度
复杂度的表示方法 O(n) O(2n) O(n²) O(log n);
在具体算法复杂度时需要注意：

• 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度
• 复杂度相加的时候，选择高者作为结果，也就是 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度
• O(1)也是表示一个特殊复杂度，即任务与算例个数无关
  时间复杂度与代码的结构设计高度相关
  空间复杂度与代码中数据结构的选择高度相关

降低时间复杂度的方法

算法： 递归，二分法，排序算法，动态规划

降低空间复杂度的方法

数据结构

复杂度降低的核心方法论

降低复杂度的方法的三个步骤：

1. 暴力解法：在没有任何时间，空间约束下，完成代码任务的开发
2. 无效操作处理：将代码中的无效计算，无效存储剔除，降低时间或空间复杂度
3. 空间转移：设计何时数据结构，完成时间复杂度向空间复杂度的转移

---

4. 如何完成线性表结构下的增删查

线性表的原理，线性表对于数据的增删查操作
线性表结构的每个节点，由数据的数值和指向下一个元素的指针构成
据结构组合方式的不同，除了单向链表以外，还有双向链表，循环链表以及双向循环链表等变形

• 链表在增，删方面比较容易实现，可以在 O(1)的时间复杂度内完成
• 对于查找，需要对全部数据进行遍历

线性表 的价值在于

• 它对数据的存储方式是按照顺序的存储
• 当数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适
• 链表的翻转，快慢指针的方法，是必须掌握的内容
• 存储空间不一定是连续的

数组(顺序) 的价值在于

• 数组在连续的空间进行存储，可以直接求解出数组的长度
• 数组可以通过索引值去查找元素，然后对相应的数据进行交换操作而完成翻转

---

5. 栈：后进先出的线性表，如何实现增删查

线性表 对数据的顺序非常敏感，而且它对数据的增删操作非常灵活
在有序排列的数据中，可以灵活的执行增删操作
它的灵活性在某种程度上破坏了数据的原始顺序
在某些需要严格遵守数据处理顺序的场景下，就需要对线性表予以限制

• 限制后的线性表--
  顺序栈
  链栈

---

6. 队列：先进先出的线性表，如何实现增删查road

队列具有先进先出的特点
在面对数据处理顺序非常敏感的问题时，队列是个不错的选择

1. 定义

   • 顺序队列：内存空间顺序存储
   • 链式队列：链式结构存储

2. 时间复杂度

   • 循环队列和链式队列的新增、删除操作都为O(1)
   • 在查找操作中，队列只能通过全局遍历的方式进行，需要O(n)的时间复杂度

3. 空间性能方面

   • 循环队列必须有一个固定的长度，因此存在存储元素数量和空间的浪费问题
   • 链式队列更为灵活一些

4. 技术选型

   • 在可以确定队列长度最大值时，建议使用循环队列
   • 无法确定队列长度时，应考虑使用链式队列

---

7. 数组：如何实现基于索引的查找