栈的性质

栈满的时候要考虑上溢的情况, 栈空的时候要考虑下溢的情况.

队列的性质

设队尾指针是rear, 队头是front, 循环队列的最大长度为QueueSize, 循环队列的相关条件和公式为:

条件 代码 条件 代码
队空条件 rear==front 队满条件 (rear+1) % QueueSIze==front
入队位置 (rear+1)%QueueSize 出队条件 (front+1) % QueueSize

计算队列长度 : (rear-front+QueueSize) % QueueSize

二叉树的性质

节点与度的关系

设k为节点数, 则整个树的度为k-1, 分别考虑节点数量和度数量有

k = n0 + n1 + n2
k-1 = 2*n2 + n1

求解上式可得

n0 = n2 + 1

即度为0的节点数为度为2的节点数加1

二叉树的种类

完全二叉树: 对于深度为K的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.
注意: 完全二叉树在给定深度的情况下, 存在最多节点和最少节点两种情况

二叉排序树: 左右子节点和根节点满足排序关系的树, 也就是最基本的树

树转森林与森林转树

  1. 将树通过儿子兄弟表示法变成二叉树
  2. 由于根节点右子树为空, 因此依次连接所有的树
  3. 二叉树转森林过程相反, 断开所有右子树的连接即可

B树

对于m阶B树

  1. 每个节点至多有m个节点
  2. 除了根节点与叶节点外, 每个节点至少有 m/2向上取整 个节点
  3. 根节点至少有两个节点
  4. 所有叶子节点在同一层
  5. 有k个子节点的非根节点包含k-1个关键码

平衡二叉树

查找表

静态查找表（Static Search Table）：只作查找操作的查找表.
A：查询某个“特定”数据元素是否在查找表中；
B：检索某个“特定”数据元素和各种属性.

动态查找表（Dynamic Search Table）：在查找过程同时插入查找表中不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素.
A：查找是插入数据元素；
B：查找时删除数据元素.

最优二叉树

最优二叉树就是从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树, 使树的权值最小.
最优二叉树是带权路径长度最短的二叉树, 典型代表是*哈夫曼树

胜者树与败者树

假设数据直接进行比赛, 中间节点记录比赛的胜者信息, 由此构成的树称为胜者树. 借助于这一结构, 可以快速的找到一组数据中的最大值, 并且可以不断的插入和删除数据

堆的性质

堆一般构造成完全二叉树的结构, 但这只是为了计算简便, 也可以构造满足堆要求但不是完全二叉树的结构

哈希表

冲突解决算法

  1. 开放地址法: 根据某种规则使用其他的位置, 例如线性探查法, 平方探查法
  2. 再哈希法: 使用另外的哈希函数在此计算, 包括
  3. 拉链法: 也称为链地址法, 即使用链表
  4. 建立公共溢出区

开放地址法可以将所有数据都存放在哈希表的数组中, 而不必引入额外的链表结果, 因此结构上更简单. 但是非常不适合需要删除数据的情况. 当删除数据时, 除了删除当前元素, 还需要妥善的处理之前由于碰撞而放到其他地方的元素. 无论是移动元素还是加入DELETE标记, 都会引入额外的开销.

图的性质

基本概念

图的表示方法: 对于图 G=(V, E) 有两种表示方法, 分别是邻接链表和邻接矩阵, 当边的数量\(E\)远远小于\(V^2\)时(即稀疏图), 使用邻接链表表示法更加紧凑, 反之可能使用邻接矩阵更加简单. 此外如果希望快速判断两个节点之间是否联通, 使用邻接矩阵也更快.

由于两种存储方式的差异, 可以认为邻接链表的空间复杂度为\(O(V+E)\), 而邻接矩阵的空间复杂度为\(O(V^2)\). 由于很多图的操作本质上是对图的数据结构的遍历, 因此存储结构的差异也决定了这些操作的时间复杂度.

邻接表: 邻接表是表示了图中与每一个顶点相邻的边集的集合
邻接多重表: 与邻接表的差别, 仅仅在于同一条边在邻接表中用两个节点表示, 在邻接多重表中只用一个节点

注意: 边的数量与度的区别, 无向图中一条边会计算两次度

入度与出度: od表示初度, id表示入度

邻接表的边结点是指示弧尾到弧头, 而逆邻接表的边结点指示弧头到弧尾, 所以有多少条边就有多少个结点, 一一对应, 逆邻接表中边节点个数等于邻接表边结点个数

拓扑排序

拓扑排序有两种计算方式, 通常的拓扑排序可以表述为, 依次从图中选择入度为0的边, 将其从图中移除并输出该节点. 以下图为例, 可以依次

  1. 输出节点1, 移除节点1指向2和4节点的边
  2. 输出节点2, 移除节点2指向3和4节点的边
  3. 省略后续操作…

拓扑排序也可以用深度优先遍历算法完成. 此时深度优先算法在递归开始前和递归结束后都需要给每个节点一个遍历的时间戳, 然后按照结束时间戳的大小进行排序输出. 对上面的图遍历结果如下图所示:

其中括号内数字表示开始遍历和结束遍历时的时间戳大小.

拓扑排序算法和深度优先遍历都可以实现有向无环图的拓扑排序, 但针对有环的情况, 拓扑排序能够探测到环的存在, 而深度优先遍历无法探测到环的存在.

最小生成树

最小生成树有两个算法, 分别是Kruskal算法和Prim算法. Kruskal算法通过不断合并两个集合完成最小生成树的构建, 而Prim通过不断加入新的点来实现最小生成树的构建.

流量计算

技巧： 按层计算, 瞻前顾后

首先计算每一层向终点方向的最大输出能力, 不包括回流的量
然后计算总体的最大流量, 为各个层中流量最小的一层的流量

本题中分为三层：
第一层为s. 朝终点最大输出量为11+22+10 = 43
第二层为节点1、2、3. 朝终点最大输出量为10+17+14 = 41（10是因为节点4最多接受10, 出度为10, 14是因为节点3的入度为14, 所以是14而不是16）
第三层为节点4、5、6. 朝终点最大输出量为10+16+16 = 42
所以综合考虑总体最大的流量只能41.

拓扑排序

拓扑排序算法将一个有向, 无环图 排列成一个有序序列.

图的深度优先遍历有一个特点: 当一个顶点的子结点都被访问完了, 该顶点才会结束访问, 并开始向上回溯访问它的父结点的其它子结点
==> 一个顶点的结束访问时间与其子结点的结束访问时间存在先后关系 ==> 逆拓扑排序
注意: 此方案无法检测环路

关键路径

关键路径是指设计中从输入到输出经过的延时最长的逻辑路径

最小生成树

Prim算法: 从一个顶点开始, 依次选择可到的边中, 权值最小的
Kruskal算法: 对边权值进行排序, 依次选择权值最小的边, 如果这条边连接了新的点, 则加入

相比于Kruskal算法, Prim算法更适合于求边稠密的无向网的最小代价生成树

其他内容

总时差TF(Total Float):一项工作在不影响总工期的前提下所具有的机动时间, 最迟完成时间与最早完成时间之差
自由时差FF(Free Float): 一项工作在不影响其紧后工作最早开始时间的条件下, 本工作可以利用的机动时间

总时差就是拖拖拖, 可以拖多少天才做工作M, 自由时差就是早早完成, 然后在下次工作委派之前可以休息多少天

排序

排序算法 平均时间 空间 排序方式 稳定性
冒泡排序 O(n^2) O(1) In-place 稳定
选择排序 O(n^2) O(1) In-place 不稳定
插入排序 O(n^2) O(1) In-place 稳定
希尔排序 O(nlogn) O(1) In-place 不稳定
归并排序 O(nlogn) O(n) Out-place 稳定
快速排序 O(nlogn) O(logn) In-place 不稳定
堆排序 O(nlogn) O(1) In-place 不稳定
计数排序 O(n+k) O(k) Out-place 稳定
桶排序 O(n+k) O(n+k) Out-place 稳定
基数排序 O(nk) O(n+k) Out-place 稳定

空间复杂度说明:

  1. 归并排序需要一个额外的空间做合并操作
  2. 快速排序由于递归而产生对数级别的空间占用
  3. 计数排序k表示数据分布范围, 基数排序k表示数字的位数

稳定性分析:

  1. 选择排序由于直接交换位置, 因此可能导致顺序变化, 而冒泡和插入排序只移动相邻的元素, 因此顺序不变
  2. 希尔排序和快速排序显然不稳定
  3. 归并排序按照顺序划分区间, 按照顺序合并区间, 因此稳定
  4. 堆排序建立堆的过程按照堆结构交换元素位置, 因此顺序可能变化

排序方法说明:

  1. 堆排序: 首先构建一个最大堆, 依次将堆顶元素与最后一个未排序元素交换
  2. 计数排序: 已知数字位于0..99, 开一个100元素的数组, 每遇到一个数字, 数组相应位置++, 最后输出
    • 遍历数据一次, 遍历记录的数组一次, 因此时间复杂度为O(n+k), 空间复杂度为记录数组的消耗, 为O(k)
  3. 桶排序: 先将数据映射到不同的桶中, 然后对桶内数据进行排序, 最后合并所有数据
    • 桶排序是计数排序的升级版, 计数排序相当于每个数字一个桶
  4. 计数排序

基数排序的正确性

如果给定如下的一组数据, 并进行基数排序, 则排序结果如下表所示

123 234 345 532 244 332 451 321

第一轮 第二轮 第三轮
451 321 123
321 123 234
532 532 244
332 332 321
123 234 332
234 244 451
244 451 532

注意在进行第k轮排序后, 如果只看末尾的k位数字, 则这部分数据均是正确排序的. 例如经过第二轮排序后, 如果只看每个数字的末尾两位, 那么这些两位数都是正确排序的.

那么在进行第k+1轮排序时, 针对每一个桶内的数字, 第k+1位是相同的, 而末尾的k位根据顺序, 数字越小越先进入桶中, 因此经过第k+1轮排序后, 末尾的k+1位数字都是正确排序的.

根据这个性质, 可以显然的证明基数排序的正确性.

主定理

对于一个递推公式

$$T(n) = aT(n/b) + O(n^d)$$

并且令

$$f=\log_{b}{a}$$

则可以通过比较f与d的大小关系获得递推式的时间复杂度

相对关系 时间复杂度
f > d \(O(n^f)\)
f = d \(O(n^f \log{n})\)
f < d \(O(n^d)\)

最后更新： 2024年04月24日 15:50

版权声明：本文为原创文章，转载请注明出处

原始链接： https://lizec.top/2020/11/29/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%9F%A5%E8%AF%86%E5%BA%93/