一. 算法与数据结构
算法：用系统的方法描述解决问题的策略机制
数据结构：计算机存储与组织数据的一种方式，可以用来高效地处理数据
程序：算法 + 数据结构
评判标准：多快好省（查询快，省内存）
二. 运行时间表示
-
什么是大O表示法：
- O（order of）
- 执行完成某项策略需要多少个步骤，可以使用大O表示法表示
-
常见的大O运行时间：
- O(log n)，也叫对数时间，二分查找，以2为底，想要的结果n为幂
- O（n），线性时间
- O（n*log n)， 快速排序
- O(n^2) ，选择排序
- O（n!），旅行商问题
-
注意：
- 算法的速度指的是操作数的增速（随着输入的增加，运行时间以什么样的速度增加），而非时间
三. 结构
- 线性结构
- 给定起始索引并以固定的步长表示的数据结构。适合快速查找数（O(1)速度)
- 中间插入数据缓慢（O（n））插入数据索引后面的数据需要重新计算索引。
- 空间固定，当需要扩容的时候，会先扩大为初始空间的两倍，并将先前的数据拷贝到新的空间。
- 单链表
- 给定起始索引，并且起始块的末尾指向下一个块。查找数据比较缓慢，中间插入数据快速。
- 双链表
- 解决单链表的逆序查找问题，给定上一个数据的索引。查找数据缓慢，中间插入数据快速。
- 哈希表
- 提供快速的插入操作和查找操作（O(1))
- 利用建key的hash值，和固定空间的size取余后得到索引（无序）。并根据索引防止key,value值。
- 哈希冲突
- 线性探查
- 二次探查
- 线性表与链式表结合
- 哈希扩容-重哈希（Rehashing）
- 树结构
- 包括节点和边的层级结构
- 根节点(root): 树的最上层的节点，任何非空的树都有一个节点
- 路径(path): 从起始节点到终止节点经历过的边
- 父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
- 孩子(children): 每个节点由边指向的下一层节点
- 兄弟(siblings): 同一个父亲并且处在同一层的节点
- 子树(subtree): 每个节点包含它所有的后代组成的子树
- 叶子节点(leaf node): 没有孩子的节点成为叶子节点
- 树的遍历
- 广度：一层一层的遍历
- 深度：先一枝遍历完再遍历另一枝
- 包括节点和边的层级结构
- 堆：完全二叉树
- 最大堆：对于非叶子节点，其存储的值比它的叶子节点大，也就是说根节点的值最大
- 最小堆：和最大堆相反，对于非叶子节点，其存储的值比它的叶子节点小，也就是说根节点的值最小
四. 顺序
- 先进先出：队列
- 后进先出：栈
- 头尾都能进能出：双端队列
五. 递归与栈
- 递归
- 基线条件，递归结束的条件
- 压栈，后进先出
六. 查找
- 线性查找
- 一个一个的排除下去
- 二分查找
- 将排序后的数据按照索引进行查找
七. 排序
- 冒泡排序
- 通过将最大的数字排到最后，第二大的数字排到倒数第二的方式进行排序（逐级比较）一次找一个数
- 或者将最小的数字排到最后，第二小的数排到倒数第二的方式逐级比较排序
- 选择排序
- 每次选择最小或者最大的值放在已排序的数的后面
- 插入排序
- 将数据分为已排序和未排序两部分，将未排序中的数值选择一个和已排序的数据再进行一次排序
- 归并排序
- 分成一个个的元素再进行排序合并
- 快速排序
- 分成以一个有序的元素并合并
