数据结构与算法
参考
- https://www.yuque.com/saodai/ss8tp9
- B站视频
数据结构
- 复杂度
- 大O表示法：以算法中基本操作重复执行的次数（频度）作为算法时间点的度量，一般只要大致的计算出数量级即可
- O(1) < O(log2 n) < O(n) < O(nlog2 n) < O(n^2) < O(n^3) < O(n!) < O(n^n)
- 常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 立方阶 < 阶乘阶 < n 次方阶
- 复杂度计算规则：多项相加保留最高项；多项相乘都保留；加乘混合，则按照计算规则；系数化为1
- 时间复杂度，与循环相关
- 空间复杂度，看有没有开辟新空间，比如数组
- 渐进符号：
1. O(g(n)): 表示渐进上界，10n^2+4n+2 = O(n^2) 是成立的，因为渐进上界括号内的复杂度要大于等于等式左边的计算结果
2. Ω(g(n)): 表示渐进下界，10n^2+4n+2 = O(n^3) 是不成立的，因为渐进下界括号内的复杂度要小于等于等式左边的计算结果
3. Θ(g(n)): 表示渐进紧致界，10n^2+4n+2 = O(n^3) 是不成立的，因为渐进紧致界括号内的复杂度要等于等式左边的计算结果 - 递归的时间空间复杂度
1. 递归的时间复杂度 = 递归的次数 * 每次递归的时间复杂度
2. 递归的空间复杂度：如果递归中有变量声明赋值，则相当于 长度为递归次数的数组
3. 递归式主方法：
- 理论基本没看懂，放弃了！！！
- 做题方法估计：参考（https://www.yuque.com/saodai/ss8tp9/hs1a1p#YN4pz）
- 假如题目给了一个递归式的表达式长得像 T(n) = aT(n/b) + f(n) 那么可以按照下边方法尝试一下
- 比如给了个题目 T(n) = 2T(n/2) + nlgn 让求复杂度
- 那么按照公式换算得出 a=2; b=2; f(n) = nlgn;
- 如果 f(n) 中有 lg 相关那么就套这个公式 f(n) = Θ(n^(logb a)lgk n); 将换算的数据代入， 即 nlgn = (n^(log2 2)lgk n); 得到 k = 1; 然后再代入到 这个公式 T(n) = Θ(n^(logb a)lgk+1 n) 得出 T(n) 复杂度为 nlg2n
- 若果 f(n) 中没有 lg 则直接代入到 T(n) = Θ(n^(logb a))
- 线性表
- 线性关系：具有单一前趋和后继的数据关系，元素一个接一个的排列
- 线性表：最简单基本常见的线性数据结构，通常表示为 (a1,a2,…an)
- 线性表特点：‘第一个元素’、‘最后一个元素’都是唯一且只有一个的；除第一个元素只有后继，最后一个元素只有前趋外，其余元素都含有前趋和后继
- 线性表顺序存储：指用一组连续的存储单元，一次存储线性表中的数据，也就是说物理位置相邻
1. 优点：可随机存取表中元素，查询效率高
2. 缺点：插入和删除需要移动元素，删除插入效率低，表长为 n, 插入新的值平均移动 n/2; 删除值平均移动 (n-1)/2
3. 顺序表插入元素时间复杂度：顺序表最后插入 O(1); 顺序表首位插入O(n);平均复杂度O(n)
4. 顺序表删除元素时间复杂度：顺序表最后一位删除 O(1); 顺序表首位删除 O(n); 平均复杂度O(n)
5. 查找元素时间复杂度：直接根据数组下标查询，所以为 O(1) - 线性表链式存储：通过指针链接起来节点，来存储数据元素，分为数据域+指针域；数据元素的节点地址不是连续的，节点空间在需要的时候才申请
1. 若节点只有一个指针域，则成为线性链表或单链表
2. 头节点：不存储数据(!!也可以存储链表长度)，只存储链表第一个节点的地址
3. 头指针、尾指针：有了尾指针就可以直接从尾部遍历查找，有了尾指针时间复杂度会有变化
4. 连式存储插入元素时间复杂度：首位插入 O(1); 末位插入 O(n); 平均复杂度 O(n)
5. 连式存储删除元素时间复杂度：首位删除 O(1); 末位删除 O(n); 平均复杂度 O(n)
6. 连式存储查找元素时间复杂度：首位查找 O(1); 末位查找 O(n); 平均复杂度 O(n) - 循环单链表：就是在单链表的基础上，尾部节点的指针指向头部节点，时间复杂度与单链表一致
- 双链表：每个节点指针不但指向后驱节点，还会指向前趋节点，也就是一个节点即知道前一个节点地址也知道后一个节点的地址
- 栈
- 栈的定义：只能通过访问它的一端来实现数据存储和检索的一种线性数据结构
- 栈的修改按照先进后出，后进先出的原则进行，插入和删除操作的一端称为栈顶Top,另外一端称为栈底，不含元素的称为空栈
- 理解：可以将栈想象成一个杯子，先进先出，与 递归的执行过程类似
- 栈的链式存储：用链表作为存储结构的栈，也称为 链栈，不必设置头指针，链表的头指针就是栈顶指针
- 队列
- 队列的定义：一种先进先出的线性表，只允许在表的一端插入值，在另一端删除元素
- 顺序队列：使用顺序存储的队列，需要设置队头指针和队尾指针
- 循环队列：可处理顺序队列中插入值溢出越界，只需要改变队头和队尾指针即可，避免采用线性表插值导致的遍历
- 队列链式存储
- 双端队列：入队出队在两端都可以进行
- 两个栈可以模拟一个队列，但是两个队列无法模拟一个栈
- 串
- 串是一种特殊的线性表，其数据元素为字符，是由字符构成的有限序列，例如： ‘abc’
- 空串：长度为零，不包含字符
- 子串：串中任意长度的连续子串构成的序列 ‘abc’ 的 子串可以是 ‘ab’ 但不能是 ‘ac’
- 串比较：两个串比较时以字符的 ASCII 码值作为依据
- 串的模式匹配：可以理解为JS 中所要的效果 a.indexOf(b)
1. 复杂度：主串长度 n , 子串长度 m
2. 最好情况（首位即匹配成功）：复杂度 O(m) | O(1)
3. 最坏请款（比较到最后 m 位）：复杂度 O(n*m) => (n-m+1)*m
4. 平均复杂度：O(n+m) - 串的模式匹配 KMP 算法：
1. 串的前缀：包含第一个字符，但是不包含最后一个字符的子串
2. 串的后缀：包含最后一个字符，但是不包含第一个字符的子串
3. KMP：可以提高串的模式匹配效率，时间复杂度为：O(n+m)
4. KMP next 的数值计算：第i个字符的 next 值 = 第i个字符前的字符串中，”串前缀===串后缀“最长的那个的长度 + 1；其中 next[1] = 0 - 数组
- 一维数组：
1. LOC: 表示第一个元素的首地址；L: 表示每个元素的大小
2. 计算数组中某个元素i的地址：ai = LOC + i*L - 二维数组：
1. 二维数组的存储，会将将第二行在第一行后边连续存储（列优先存储，则第二列在第一列存储之后连续存储）
2. LOC: 表示第一个元素的首地址；L: 表示每个元素的大小; N: 行数; M: 列数；
3. 计算二维数组 [i][j]的地址 = LOC + ([i][j] 前有多少个元素) * L
- 行优先存储：LOC + (i*M + j) * L
- 列优先存储：LOC + (j*N + i) * L
- N == M 且 i == j 时，按行还是按列的地址都是一样的，偏移量也是一样的
- 矩阵
- 对称矩阵：矩阵内任意元素具有 Ai,j = Aj,i 的特点，
1. 按照主对角线对称，分为上三角区和下三角区
2. 存储时只需要存储下三角区 + 主对角线即可，一般使用一个一维数组存储
3. 按行存储：i >=j 时 Ai,j = (i+1)i/2 + j + 1; i < j 时，因为是主对角线堆成 则可以改为计算 Aj,i - 三对角矩阵
1. 只有主对角线两侧紧邻区域有值，其他区域都是 0
2. 存储时只存中间区域的值，不存 0 的位置，存到一个一维数组中
3. 按行存储：Ai,j = 2i+j+1 - 稀疏矩阵
1. 矩阵很大，但是存的非0 元素很少
2. 压缩存储方式：使用三元组顺序表存储 [i, j, data] [行, 列， 值]
3. 另一种压缩方式：十字链表 - 树
- 一种非常重要的非线性结构，一个元素可以有0个或多个的后继元素
- 树是n个节点的有限结合，n=0 时称为空树，有且只有一个根节点
- 兄弟节点：具有相同父节点的节点
- 节点的度：一个节点的子树的个数计为该节点的度
- 叶子节点：终端节点，没有子节点的节点，度为 0 的节点
- 内部节点：分支节点，度不为0的节点
- 节点的层次： 根为第一层，跟的子为第二层，以此类推
- 树的高度：一棵树最大的层数计为树的高度或者树的深度
- 树的度：树中所有节点度的最大值
- 树的性质
1. 树中节点总数 = 所有节点的度数之和 + 1
2. 度为m的树中第i层上最多有 m^(i-1) 个节点，最多的情况就是每层都有 m 个节点
3. 高度为 h 的 度为 m 的树，最多有 (m^h - 1)/(m-1) 个节点，最多的情况就是每层都有 m 个节点，一共 h 层
4. 具有 n 个节点度为 m 的树的最小高度为 logm (n(m-1) + 1) ，要想高度最小，那还是每层都要有 m 个节点 - 二叉树
- n 个节点的有限集合，n=0 时为空树，或者是由一个根节点及两个不想交的且分别称为左右子树的二叉树组成
- 树和二叉树的区别
1. 二叉树中子树分为左子树和右子树，即使只有一个子树也要区分左右
2. 二叉树中节点最大度数为2 - 二叉树的性质
1. 二叉树第i层最多有 2^(i-1) 个节点，实际就是树的公式中国将度==2 后代入
2. 高度为 h 的二叉树最多有 2^h - 1 个节点；最多的情况下，每一层的节点数都是前边所有层的节点数+1
3. 任意一个二叉树，度数为0的叶子节点个数 = 度数为2的节点个数 + 1；由 ”树中节点总数 = 所有节点的度数之和 + 1“ 推断出来的
4. 有 n 个节点的完全二叉树的高度为 (log2 n + 1)的向下取整或者 (log2 (n+1)) 的向上取整 - 满二叉树：高度为 k 的二叉树，如果有 2^k -1 个节点，那就是满二叉树，可以从上往下，从左往右编号
- 完全二叉树：除最后一层外，其他层都是”满的“，最后一层的节点也是从左至右依次放置；这个情况下，完全二叉树中的每一个节点都能与同样深度的满二叉树一一对应
- 卡特兰数：n 个节点的二叉树有多少种: (C2n n)/(n+1); 其中 (Cn m) = n!/m!*(n-m)!
- 二叉树的顺序存储
1. 用一组连续的存储单元，存储二叉树中的节点
2. 树节点与编号i间关系
- 求父节点：i=1,则为根节点，根节点没有父节点；若 i>1 则该节点的父节点为 i/2 的向下取整
- 求左子节点：2i<=n 则该节点左子节点编号为 2i, 否则无左子节点
- 求右子节点：2i+1<=n 则该节点右子节点编号为 2i+1, 否则无右子节点
3. 顺序存储对完全二叉树比较合适，对普通二叉树来说则为了保持关系，会有很多”虚节点“
4. 单支树，除了叶子节点，其他节点的度都为1
- 二叉树链式存储
1. 二叉链表存储，每个二叉链表节点存储 [当前节点的数据元素, 左子节点指针，右子节点指针]，如果没有对应的子节点则存NULL
2. 二叉链表存储中的有效指针域数量：即为树结构中的有效关联数量，每个子节点都仅有一个父节点(除了根节点)，因此有效的数量 = 总的节点数 - 1 个
3. 三叉列表：在 二叉链表的基础上增加了一个指向父节点的指针域 - 二叉树的遍历
1. 先序遍历：按照 根左右的次序遍历
2. 中序遍历：按照 左根右的次序遍历
3. 后序遍历：按照 左右根的次序遍历
4. 层次遍历：从根节点开始，每一层从左往右访问 - 还原二叉树
1. 单独一种遍历结果没法还原出树
2. 先序遍历和层次遍历的的首位就是根节点，后序遍历的末位也是根节点，因此 中序遍历与其他任意一种遍历结合就能还原二叉树 - 平衡二叉树：二叉树中任意节点的左右子树高度只差不大于1，完全二叉树一定是平衡二叉树
- 二叉排序树：又称二叉检查树
1. 根节点关键字：就是根节点的值
2. 根节点的关键字大于左子树的所有节点关键字
3. 根节点的关键字小于右子树的所有节点关键字
4. 左右子树也是二叉排序树，依次递归
5. 二叉排序树的中序遍历是一个有序序列
6. 计算题：会给一个关键字序列，关键字序列的收个元素就是根节点，后边数字比根大就放右边，比根小就放左边，节点为空就直接插入，不为空就与其比较后向下层插入，其他的元素依次判断插入二叉排序树中即可
7. 二叉排序树查找的效率，是受查找的层数相关的，层数越高效率越差 - 最优二叉树：又称哈弗曼树 它是一类带权路径长度最短的树
1. 路径：从树的一个节点，到另一个节点之间的通路
2. 路径长度：路径上的分支数目（几条线）
3. 树的路径长度：从根节点到每一个叶子节点路径长度之和，乘以权值则代表树的带权路径长度 - 最优二叉树构造：
1. 题：将一个权值集合（例如：{1,3,3,4}），构造成一个二叉树
2. 构造方法：
- 从前往后找两个权值最小的
- 这两个里边小的作为左子树，大的作为右子树，构造新的二叉树，这个二叉树的根的权值等于两者相加
- 将计算后的根加入权值集合末尾
- 继续上述步骤，直到集合中只剩下一个
3. 权值大的距离根节点近，权值小的距离根节点远
4. 最优二叉树只有度为 0 的节点和度为2 的节点
5. 总节点个数 = (权值数量 * 2) - 1
- 哈夫曼编码：
1. 等长编码：对每个字符编制相同长度的二进制码，例如英文26个字符，需要 2^5 即需要5位二进制串表示
2. 哈夫曼编码不是等长编码
3. 接收方按照 5 位一组将电文进行分割后，通过对应实现译码
4. 题：一般会给一串字符并说明字符的权重
- 我们根据权重画出哈夫曼树，并将节点替换为相应的字符
- 根节点与左子节点的连线为 0 ，与右子节点的连线为 1，将每条节点间连线标出
- 某个字符的编码就是从根节点开始到当前字符节点所经过路径上的 0,1 组成
5. 哈夫曼编码压缩比：即每个字符从等长编码到哈夫曼编码的压缩情况
6. 哈夫曼编码是基于贪心策略的
- 线索二叉树
7. 普通二叉树，采用二叉链表做存储结构，则链表中会有空指针域，利用这个空指针域来存放节点的前驱后继信息 - 图
- 图中，任意两个节点之间都可能有关系，一个节点可能有多个前趋或者多个后继
- 图，标记为 G(V,E) V表示顶点的非空有限集合；E是图中边的有限集合
- 有向图：每个边是有方向的，那么顶点关系用
<v1,v2> v1 是起点，v2 是终点 - 无向图：每个边是无方向的，那么顶点关系用
(v1,v2) - 完全图：每个顶点都与其他顶点有一个边，则称为完全图
1. 假设无向完全图有 n 个顶点，那完全图的边一共有 n(n-1)/2
2. 有向完全图的边总数则为 n(n-1)，因为每两个顶点间有来回两条边 - 无向图顶点的度：关联于该顶点的边的数量
- 有向图的出度与入度：出度–从该顶点指出去的边的数量；入度–指向该顶点的边的数量；总度数 = 出度 + 入度
- 图的总度数 = 边数 * 2
- 路径：就是通过那几条边的组合，实现从一个顶线到另一个顶点；路径长度就是路径上边或弧的数目
1. 第一个顶点和最后一个顶点相同的路径称为回路或者环
2. 简单路径：路径上，除了起点和终点可以相同外，其余顶点都不相同的路径 - 连通图：
2. 连通图：无向图中，任意两个顶点间都有至少一条的路径可以连通，则称为连通图
3. 对于n个顶点的无向图，最少有 n-1条边就可以实现连通，最多 n(n-1)/2
4. 强连通图：有向图中，任意两个顶点间都有来回的两条路径连通，称为强连通图
5. 对于n个顶点的有向图，最少有n条边就可以实现连通，最多 n(n-1) - 图的存储结构
1. 邻接矩阵表示法：使用一个矩阵来表示图中顶点间的关系，有n个定点的图，其邻接矩阵就是 n 阶的，矩阵中值为1表示有边，为0表示无边
2. 无向图的邻接矩阵是对称的，有向图则不一定是
3. 无向图邻接矩阵计算某个定点的度数：定点vi 的度数就是第 i 行非0元素的个数
4. 有向图邻接矩阵计算某个定点的度数：定点vi 的出度–第 i 行非0元素的个数; 入度：第 i 列非0元素的个数
5. 邻接链表表示法：为图的每个节点建一个单链表，具体的还得看图，这里不做详解
6. 有向图的邻接链表，有几个指出来的表结点就有几条边；无向图的邻接链表，有n指出来的表结点就有n/2条边
7. 稠密图和稀疏图，边多的就是稠密图，边少的就是稀疏图
8. 邻接矩阵表示法适合稠密图，邻接链表适合稀疏图 - 网：边或弧带有权值的图，称为网；网的邻接矩阵中有边的会用权值表示，没有边的用 oo 无穷表示
- 图的遍历
1. 深度优先搜素：从一个顶点A按照出度向另一个顶点B，B 在按照出度向顶点C, 这样先从路径的起始遍历到路径的末尾，然后在通过回溯，换一个路径遍历
2. 深度优先搜素的时间复杂度：n 表示顶点数，e表示边数，邻接矩阵存储的复杂度为 O(n^2)；邻接链表的时间复杂度 O(n+e)，用栈的方式
3. 广度优先搜索：先遍历一个顶点A的所有出度的节点，在遍历出度节点的所有出度节点，以此类推，相当于一层层遍历
4. 广度优先搜素的时间复杂度：n 表示顶点数，e表示边数，邻接矩阵存储的复杂度为 O(n^2)；邻接链表的时间复杂度 O(n+e)，用队列的方式 - 拓扑排序
5. AOV 网：一种有向无环图
6. AOV 网中 弧的尾部是前趋，弧指向的是后继，前趋对后继有制约关系
7. 拓扑排序：是 AOV 网中所有定点排出的线性序列，并且网中任意路径<vi,vj>的前后顶点在这个线性序列中 vi 排在 vj 前
8. 假设 AOV 图是一个工程的计划，那AOV网的一个拓扑排序就是工程顺利完成的可行方案
9. 拓扑排序计算方式：
- 在 AOV 网中选择一个入度为0的顶点，且输出它
- 在网中删除该顶点及与该顶点相关的所有弧
- 重复上述两步直到不存在入度为0的顶点为止
- 例如：得到 614325 这个拓扑序列，那么对于 6 与 4 来说，可能存在弧6->4;不可能存在弧4->6;可能存在6->4的路径，一定不存在4->6的路径
- 查找
- 查找表：由同一类型元素构成的集合，集合元素之间存在着完全松散的关系
- 静态查找表只进行以下两种操作
1. 查询某个特定元素是否在查找表中
2. 检索某个特定元素的各种属性 - 动态查找表，除了静态查找表的功能还进行如下操作
1. 在查找表中插入一个数据
2. 从查找表中删除一个数据 - 关键字是数据元素某个数据项的值，可以用来标记数据元素
- 静态查找表有：顺序查找、二分查找、分块查找
- 动态查找表有：二叉排序树、平衡二叉树、B_树、哈希表
- 查找的基本操作：将记录的关键字与给定的值进行比较
- 顺序查找：就是从左向右查找，不需要有序，适用于顺序存储和链式存储方式，平均查找长度为 (n+1)/2
- 二分查找：
1. 又称折半查找，就是将给定的值与查找表中间的值进行比较，下标求中间值（比较值），中间值为小数则向下取整，比较后舍弃中间值进行下一轮比较
2. 例如 10个值，则依次取 (1+10)/2 => 5；(6+10) => 8; (9+10)/2 => 9; (10+10)/2 => 10;
3. 需要顺序存储，且要有序存储
4. 二分查找成功时，给定值的比较次数最多为 [log2 n) + 1 向下取整
5. 二分查找的平均查找长度为：(log2 (n+1)) - 1 - 哈希表
1. 哈希表：通过计算一个已记录的关键字为自变量的函数（哈希函数），来得到该记录的存储地址
2. 根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上
3. 对于一个哈希函数，两个不同的关键字，经过哈希函数查找后的地址相同时，称为冲突，具有相同哈希函数值的关键词称为同义词
4. 一般情况下，冲突可以尽可能的减少，而不能避免，要减少冲突，就要尽可能均匀的将关键字映射到存储区的各个存储单元
5. 对于哈希表来说，主要考虑两个问题，一个是如何构造哈希函数，一个是如何解决冲突
6. 哈希函数构造方法：
- 构造哈希函数时，一般都会对关键字进行计算，尽可能的使得关键字的所有成分都起作用
- 除留余数法：H(key) = key % m = 地址； 求关键字 key 的余数作为地址，其中 m 是一个接近n但不大于n的质数，n 是散列表的长度，地址一般从 0 开始
- 其他的构造方法不介绍，也不考
7. 解决冲突的方法
1. 解决冲突就是在冲突时，给冲突的关键字再找个地址存储
2. 线性探测法：如果 H(key) 冲突了 那就按照 Hi = (H(key) + i) % m；再计算一个地址，其中 i=1,2,3,... 表示再次计算如果还是冲突就，加码再次计算，直到不冲突为止
3. 二次探测法：如果 H(key) 冲突了 那就按照 Hi = (H(key) + di) % m；再计算一个地址，其中 i=1^2,-1^2,2^2,-2^2,... 表示再次计算如果还是冲突就，就按照 1^2,-1^2,2^2,-2^2,...的方式依次尝试，直到不冲突为止,与线性探测法相比，是在 H(key) 地址的左右来回试探
4. 装填因子：a = 表中装入的记录树 / 哈希表长度，a 代表哈希表的装满程度，a 越大冲突概率越大
- 堆
- n 个关键码构成的序列{k1,k2,…kn}，满足以下关系称为堆
1. 小顶堆：ki <= k2i && ki <= k(2i+1) 即 根节点比子节点小的二叉树，层次遍历的结果
2. 大顶堆：ki >= k2i && ki >= k(2i+1) 即 根节点比子节点大的二叉树，层次遍历的结果 - 将一个序列调整为一个大顶堆或者小顶堆
1. 先按照层次遍历的结果将其还原成一个二叉树
2. 从叶子节点开始向上依次判断，比如说要还原成一个小顶堆，就要使得局部根节点的值比子节点要小，不符合的就互换一下 - 排序
- 通过排序使得关键字满足递增或者递减的关系
- 稳定的：原序列中有 Ri 和 Rj 的关键字相同，且 Ri 在 Rj 之前，经过排序算法后，还能保持 Ri 在 Rj 之前，那就是稳定的，否则是不稳定的
- 归位：在排序时能确定最终排序位置，比如 Ri 排序后应该放在位置 3，那在计算时如果开始没将它放在 3 这个位置就是不归位
- 直接插入排序
1. 新序列中以 R1 开始，遍历 原序列R, 每个 Ri, 依次与新序列中从后开始的关键字相比较，大的直接插入到后边，小的继续往前判断，直到插入
2. 直接插入排序，稳定、不归位，平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1)
3. 适用于基本有序的情况 - 希尔排序
1. 是直接插入排序算法的改进
2. 方法：
- 设定一个增量序列，例如：5，3，1
- 按照增量序列依次将原序列切割成多段，比如增量为5时，将第 0, 5, 10 位置的元素分为一组，1，6, 11 分为一组，以此类推
- 每组间元素进行直接插入排序，排序后的值互换位置，插入回原序列
- 按照增量序列依次处理，直到增量为 1
3. 希尔排序：不稳定、不归位，平均复杂度 O(n^1.3), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1)
- 计数排序
1. 适合比较少数据量的排序
2. 就是将把要排序的数统计一下每种数据有多少个，然后依次添加到序列中 - 简单选择排序
1. 从首位开始，依次用后边的关键字与当前的关键字比较，选出最小的那个与当前位替换顺序，直到最后一位为止
2. 简单选择排序: 不稳定、归位，平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n^2), 空间复杂度 O(1) - 堆排序
1. 先将原序列，按照层级遍历，成一个二叉树；然后构造一个大根堆或者小根堆；将堆的根与堆的末位进行交换，然后再次构造大根堆或者小根堆；重复进行操作，直到整个堆变成一个新的序列
2. 堆排序：不稳定、归位，平均复杂度 O(nlog2 n), 最大复杂度 O(nlog2 n), 最小复杂度 O(nlog2 n), 空间复杂度 O(1) - 冒泡排序
1. 从原序列首位开始，分别进行 ki 与 k(i+1) 位的比较，如果 如果 ki 更大则交换顺序，这样直到交换到最后一位，可以保证最后一位是最大的，重复进行
2. 冒泡排序：稳定、归位，平均复杂度 O(n^2), 最大复杂度 O(n^2), 最小复杂度 O(n), 空间复杂度 O(1) - 快速排序
1. 基于分治的思想，通过一趟排序将待排序的记录分为两个部分（前半区、后半区），前半区的关键字都不大于后半区的关键字，然后载分别对两部分进行快速排序，依次递归操作
2. 基本有序序列的快速排序效率最低，时间复杂度最大 O(n^2)
3. 快速排序：不稳定、归位，平均复杂度 O(nlog2 n), 最大复杂度 O(n^2), 最小复杂度 O(nlog2 n), 空间复杂度 O(log2 n) - 归并排序
1. 基于分治的思想，将一个序列一分为二，每一半再一分为二，如此递归，直到每一项为1个，在从从底向上，每两项间进行比较、每四项间进行比较，如此向上递归，直到最外层；
2. 归并排序：稳定、归位，平均复杂度 O(nlog2 n), 最大复杂度 O(nlog2 n), 最小复杂度 O(nlog2 n), 空间复杂度 O(n)
算法
主要记录一些上午题概念，下午题中的 c 语言算法部分基本放弃~
- 回溯法
- N 皇后问题：给定 N * N 的棋盘，要在棋盘上摆放N个皇后，皇后中的任意两个都不处于同一行，同一列，同一对角线上
- 判断是否同一列：Qi列 == Qj列；判断是否在一个对角线：|Qi行 - Qj行| == |Qi列 - Qj列|
- 代码求解 N 皇后问题
1. 非递归（循环、迭代）
2. 递归 - 深度优先
- 主要考的是下午C 语言计算题，放弃。。。
- 分治法
- 用递归来实现的
- 递归是指自己调用自己，或者间接的自己调用自己，有两个基本要素：1.需要有边界条件（递归出口），2.递归模式（递归体）
- 分治法的基本思想：
1. 规模越小，解题所需时间越少，越容易处理
2. 将一个难以解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之 - 分治算法三个步骤：
3. 分解：原问题分解为子问题
4. 求解：递归求解各个子问题
5. 合并：子问题的解合并成原问题的解 - 动态规划法
- 与分治法类似，基本思想都是将问题分解为若干个子问题，然后求解子问题，在通过子问题的解得到原问题的解
1. 不同点：适合动态规划法的问题分解为的子问题往往不是独立的（有相同的子问题）
2. 操作上，将动态规划法会用一个表记录所有已解决的子问题答案，在后续计算中如果有相同的问题，则直接找出已求解的答案，避免重复计算 - 动态规划算法，通常用来求解某种最优性质的问题（全局最优解）
- 适合动态规划法求解的问题的两个特征：
3. 最优子结构：一个问题的最优解中包含其子问题的最优解（需要注意，贪心算法也有这个特性）
4. 重叠子问题：原问题的递归算法可反复的解同样的子问题，对每个子问题只解一次，保存在表中，需要时查表 - 0-1 背包问题
5. 问题详情表：n个物品，第 i 个物品价值为 vi, 重量 wi, 背包容量 W，如何装，使得背包物品价值最大
6. 0-1 表示物品要么装入，要么不装入
7. 代码实现：放弃~~~
8. 背包问题时间复杂度：O(n * w); 空间复杂度：O(n * w) - 矩阵连乘：
9. 由动态规划法实现
10. 时间复杂度：O(n^3); 空间复杂度：O(n^2)
11. 计算方法:
- 矩阵 A(mn) 与 B(np) 相乘所需的乘法次数为 m * n * p
- 相乘后的结果可以类似表示为 AB(mp) ，再次与 C(pk) 相乘则所需乘法次数为 m * p * k
- 因此 A(mn), B(np), C(p*k) 三者相乘的乘法次数可以为 m * n * p + m * p * k
- 多个矩阵连乘，最优的计算次序是先将 m, n, p, k 中最大的那个乘以，消除掉
- 贪心法
- 贪心法与动态规划法类似，也用来解决最优化问题，但是在解决问题的策略上，贪心法不是从整体最优上考虑，而是局部最优
- 适合贪心法求解的问题的两个特征：
1. 最优子结构: 一个问题的最优解中包含其子问题的最优解（需要注意，贪心算法也有这个特性）
2. 贪心选择性质：问题的整体最优解，可以通过一系列局部最优的选择，即贪心选择来实现 - 部分背包问题
3. 在 0-1 背包问题基础上，物品可以部分装入背包 - 分支限界法
- 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的方法，用来找出满足约束条件的一个解
- 搜索方式上采用广度优先或以最小消耗优先
|