-
复杂度
- 程序执行时所需要的计算量和内存空间（与代码是否简洁无关）
- 复杂度是数量级，不是具体的数字
- 一般针对一个算法，而不是一个完整的系统
-
时间复杂度（数量级）
- o(1) 一次
- o(n) 与传输的数据量一样
- o(n^2) 数据量的平方
- o(logn) 数据量的对数
- o(n*logn) 数据量 * 数据量的对数
-
空间复杂度（数量级）
- o(1) 一个单位
- o(n) 与数据量一样大的单位
-
栈和数组的区别
- 栈：逻辑结构。理论模型，不管如何实现，不受任何语言的限制
- 数组：物理结构。真实的功能实现，受限于编程语言
-
链表和数组的区别
- 链表是一种物理结构(非逻辑结构), 类似于数组
- 数组需要一段连续存储的内存区间, 而链表是零散的
- 链表的数据结构为{value, next?, prev?}
- 链表: 查询慢 o(n), 新增和删除快o(1)
- 数组: 查询快 o(1), 新增和删除慢o(n)
-
数据结构的选择，要比算法优化更重要
-
要有时间复杂度的敏感性，比如length不能遍历查找
-
凡有序，必二分！！ 凡二分，时间复杂度必包含o(logn)！！！
-
优化嵌套循环，可以考虑使用“双指针”
-
二叉搜索树BST：查找快，增删快
-
平衡二叉树
- 如果BST不平衡，则会变成链表
- 所以要尽量平衡：平衡二叉搜索树BBST
- BBST增删查，时间复杂度都是o(logn)，即树的高度
-
堆栈模型
- 值类型变量，存储在栈
- 引用类型变量，存储在堆
-
堆
- 完全二叉树
- 最大堆： 父节点 >= 子节点
- 最小堆： 父节点 =< 子节点
-
堆的逻辑结构是一棵二叉树，但物理结构是一个数组
-
堆 vs BTS
- 堆的查询比BST慢
- 增删比BST快，维持平衡更快
- 但整体的时间复杂度都在o(logn)级别，即树的高度
-
堆的使用场景
- 特别适合“堆栈模型”
- 堆的数据，都是在栈中引用的，不需要从root遍历
- 堆是数组形式，根据栈的地址，可用o(1)查找到目标
-
动态规划
- 把一个很大的问题，拆解为很多个小问题，逐级向下拆解
- 用递归的思路去分析问题，再改为循环来实现
-
尽量不要转换数据结构，尤其是数组这种有序结构
-
尽量不要使用内置api，如reverse，不容易识别出复杂度
-
数字操作最快，其次是字符串
-
慎用正则
-
栈： 一种先进后出的数据结构
-
队列：一种先进先出的数据结构
-
链表：不是连续的数据结构，而是由一系列的节点组成，节点之间通过指针连接
-
树： 是一种有序的层级结构。每个节点下面可以有若干个子节点。例如常见的 DOM 树
-
二叉树：首先它是一棵树，其次它的每个节点，最多有两个子节点，分别为 left 和 right