基本计算 对角矩阵存在交换律，即 $\bigwedge_1 \bigwedge_2=\bigwedge_2 \bigwedge_1$
注意交换位置
对于 AB=C B & C均按列分块，则$A(\beta_1 \beta_2 \beta_3)=(\gamma_1 \gamma_2 \gamma_3)$，故B的列向量都是$AX=\gamma$ 的解，特别的，当AB=O即C=O时，B的列向量均是 $AX=0$ 的解。 B & C按行分块，则 AB的行向量均可由B的行向量线性表出。 A & C按列分块，则 AB的列向量均可由A的列向量线性表出。[2013] 规律1与解联系起来，尤其是AB=O推出B的列向量是Ax=0的解这一规律，除此之外AB=O也经常用r(A)+r(B)≤ n这个不等式。
“AB=O” 👉 方程的解(B的列向量是A的解)
👉 秩 r(A)+r(B) ≤ n (n为A的列,B的行)
规律2,3与线性表出关联，进而可以跟秩，向量组等价(能互相线性表出则等价)联系起来。
几个特殊符号 $a(a_1,a_2,a_3)^T$
矩阵: $ab^T$ = $(ba^T)^T$
$r(ab^T)$ ≤ $r(a)$ ≤ 1
任何两行成比例
$aa^T$: 对称矩阵
数: $a^Tb = b^Ta$: $ab^T$ 或 $ba^T$的绩(主对角线元素之和)...
计算※ 数字型 题型 注意“存在三条对角线的情况”，通过 逐行相加 的到 “三角型”计算
经典例题 2008-真题
抽象型 题型 行列式性质恒等变形 矩阵公式、法则恒等变形，E恒等变形 形特征值、相似 经典例题 思路：利用单位矩阵恒等变形
思路一：利用矩阵相似（$\alpha_1，\alpha_2，\alpha_3$无关，后面出现$A\alpha_1，A\alpha_2，A\alpha_3$想到相似）
利用乘法公式凑$PAP^{-1}=B$
思路二：用行列式性质
思路：“不可逆”=>“行列式为0”=>观察看到为特征值形式$|\lambda E-A|=0$，利用特征值与行列式的关系求解
应用 特征值 思路 “消0且得公因式”
例题 对于特征多项式应两行（或列）加加减减，至多是三行（或列）的加加减减找出 $\lambda-a$ 的公因式，然后再解一个二次方程，就可求出矩阵A的三个特征值
克拉默法则 思路 不用来解大的方程组，常用小的证明题，
齐次方程AX=0有非零解→ |A|=0 齐次方程AX=0没有非零解→ |A|≠0 经典例题 image-20210811155745415
“AB=O” 👉 方程的解(B的列向量是A的解)
👉 秩 r(A)+r(B) ≤ n (n为A的列,B的行)
矩阵秩 注意点 r(A) = r 👉A中有r阶子式不为0,任何r+1阶子式(若还有)必全为0....
寻址方式 基本寻址方式 特 征 优 点 缺 点 备 注 隐含寻址 操作数的存放地由操作码决定 立即寻址 操作数直接在指令中 加快执行速度 增加指令长度，不方便修改操作数 适用提供常数，设定初始值 寄存器寻址 操作数在指令指定的寄存器中 方便修改，访问寄存器加快指令执行，缩短指令长度，编程更灵活 直接寻址 操作数地址在指令中，操作数在主存单元中 指令字较长，不方便地址修改 间接寻址 操作数地址的地址在指令中，操作数在主存中 方便修改指针，编程更灵活 访问两次主存获取操作数，降低执行速度 形式地址，有效地址EA(=操作数地址) 寄存器间接寻址 操作数地址在指令指定的寄存器中，操作数在主存单元中 压缩指令长度，修改寄存器内容就可以修改主存地址指针 方便编写循环程序 相对寻址 操作数地址由PC和指令提供的地址偏移量决定,操作数在主存单元中 EA=PC+D，适用与地址无关的程序设计 基址寻址 操作数地址由基址寄存器(RB)和指令提供的地址偏移量决定，操作数在主存单元中 缩短指令长度，扩大寻址空间 大型计算机，用户的逻辑地址→主存的物理地址，EA=(RB)+D 变址寻址 操作数地址由变址寄存器(RI)和指令提供的地址偏移量决定，操作数在主存单元中 寻址到操作数RI内容(地址)自动修改，EA=(RI)+D 堆栈寻址 寻址方式由指令操作码决定 适用涉及堆栈操作的指令，EA=(SP) 基本寻址方式示意图...
外部排序 由于数据元素太多，无法一次全部读入内存进行内部排序，这是就要通过外部排序来解决
1.外排原理 目的：通过内存的读写操作(每次读写操作都是成块的进行，比如每次1KB)，将存放于磁盘中的大量数据变得有序。
(拿二路归并举例)
如图，对于在磁盘中分块存放的数据，每块存入三个元素，共16块
在内存中建立三个缓冲区输出缓冲区、输入缓冲区1以及输入缓冲区2
1.1构造初始归并段 首先，依次地读入前两块数据，分别存入内存中的 缓冲区1、缓冲区2
将输入缓冲区1以及输入缓冲区2中存放的数据经过 内存中的二路归并排序(内排)后，将生成的有序的块经 输出缓冲区 写入磁盘 得到一个有序的归并段
同样的，对剩余块进行同样的操作可以得到
1.2以归并段为单位进行归并 分别选取归并段1和2中较小的一块，依次读入至缓冲区1,2
内排之后，写入内存，注意，输入缓冲区1(或2)空缺后要立即在归并段1(或2)中读入新的块到其中进行归并排序
（以保证输出缓冲区始终输出归并段中较小的元素）
最终，完成所有归并段的第一趟归并之后，会有
之后，4块成一个归并段，两两归并
……
最终。经过3趟归并，整体会变得有序！
2.优化思路 2.1时间开销分析 在整个排序过程中，时间开销分析如下
可以看到，
外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间
而读写外存时间是关键的时间开销，因此优化应该针对怎么减少读写外存的次数展开
而文件总块数无法优化，只能针对归并的趟数优化
为此，我们需要采用多路归并来解决
2.3结论 2.4 优化思路一：采用多路归并 对上面的例子，如果采用四路归并
只需96次读写即可！！
2.5 优化思路二：减少初始归并段数量r 败者树 归并段数增加之后，内存中缓冲区数目增加，从中对比得出最小关键字的对比次数也会随之增多……
1.算法思想 构造 如图所示的树结构，叶节点对应（脑补）各归并段（假设共有8个归并段），分支结点记录败者来自哪个归并段，最后根节点记录冠军来自哪个归并段，并且将冠军输出，为这8个归并段中的最小值。
下轮选择冠军记录的那个归并段（归并段3）中的元素6，代替1的位置，如图，并依次向上的与各败者结点对比，胜则往上，败则留下，最终输出冠军
接下来，循环这个过程
2.效率分析 对于k路归并，第一次构造败者树需要对比关键字k-1次 有了败者树，选出最小元素，只需对比关键字次$\left \lceil \log_2k \right \rceil$
置换选择排序 ⽤于内部排序的内存⼯作区WA可容纳l个记录，则每个初始归并段也只能包含l个记录，若⽂件共有n个记录，则初始归并段的数量r=n/l,这是之前的做法 1.算法思想 设初始待排文件为F，初始归并段输出文件为FO，内存工作区为WA,FO和WA的初始状态为空，WA可容纳w个记录。置换选择算法的步骤如下： 1）从F输入个记录到工作区WA。 2）从WA中选出其中关键字取最小值的记录，记为 MINIMAX记录3）将MINIMAX记录输出到FO中去。 4）若F不空，则从F输入下一个记录到WA中。 5）从w中所有关MINIMAX键字比记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。 6）重复3）~5），直至在A中选不 MININ出新的记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。 7）重复2）~6），直至WA为空。由此得到全部初始归并段。
最佳归并树 利用置换选择排序构造初始归并段，归并段长短不一...
排序算法 平均时间复杂度 空间复杂度 稳定性 适用情况 插入排序 $O(n^2)$ O(1) 稳定 n较小，初始序列基本有序 希尔排序 $O(n^{1.3})$ O(1) 不稳定 冒泡排序 $O(n^2)$ O(1) 稳定 n较小，初始序列基本有序 快速排序 $O(n\log_2n)$ $O(nlog_2n)$ 不稳定 初始序列无序 简单选择排序 $O(n^2)$ O(1) 不稳定 n较小 堆排序 $O(n\log_2n)$ O(1) 不稳定 n较大或只排前几位 2-路归并排序 $O(n\log_2n)$ O(n) 稳定 n很大 链式基数排序 $O(d(n+rd))$ $O(rd)$ 稳定 n大，关键字值小 相关概念 1....
顺序查找 1 2 3 4 5 6 7 8 9 10 11 typedef struct{//查找表的数据结构（顺序表） int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int Seq_Search(SSTable ST,int key){ ST.elem[0]=key; int i; for (i = ST.TableLen;ST.elem[i]!=key ; i--) {}//从后往前查找，最终返回下标i return i;//返回0说明没找到 } 效率分析 对于长度为n的顺序表，如果查找成功 $$ ASL={\frac{1+2+…+n}{n}}=\frac{n+1}{2} $$ 若果查找失败，则 $ASL=n+1$
总体上，该算法时间复杂度为 $O(n)$
优化思路 1.如果使得表中的元素有序存放……，可以构造出一棵查找判定树
此时，查找失败时$ASL=\frac{1+2+…+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$
优点： 容易查找失败时ASL更小
2.如果各元素被查找的概率不同……，可以把概率大的靠前
优点： 容易查找成功时ASL更小
折半查找 折半查找，又称“二分查找”，仅适用于有序的顺序表。
针对升序排列的顺序表，代码实现如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 typedef struct{//查找表的数据结构（顺序表） int *elem;//动态数组基址 int TableLen;//查找表长度 }SSTable; int BinarySearch(SSTable L,int key){ int low=0,high=L....
一、最小生成树 📌什么是生成树？ 连通图的生成树是包含图中所有顶点的一个极小连通子图，通俗地讲，就是“边尽可能少，但需保持连通”。
规律： 对于一个顶点数|V|=n的树，其生成树的边数|E|=n-1。如果将|E|+1，必然会形成回路；如果将|E|-1，则会成为非连通图。
📌什么是最小生成树？ 最小生成树，也称最小代价树(Minimum Spanning Tree，MST)
是带权连通无向图的生成树中边的权值之和最小的一棵树，联系实际问题不难理解其中“最小代价”的意味。
Prim（普利姆算法），Kruskal（克鲁斯卡尔算法）就是寻找最小生成树的常用算法。
1.Prim（普利姆算法） 从某一顶点开始，每次将代价最小的新顶点纳入生成树，直至所有顶点都纳入为止。
图示 截图_20210529120539
易知，此方法得到的最小生成子树是不唯一的。
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void MiniSpanTree_PRIMI(Graph G,int u){ //从顶点u出发找G的最小生成树 for (int i = 0; i <G.vexnum; ++i) {//辅助数组初始化 if(i!=u){ closedge[i]={u,G.arcs[u][i]}; } } closedge[u].lowcost=0; for (int j = 0; j < G.vexnum; j++) { k=minimum(closedge);//求生成树的下一个节点 cout<<cloedge[k]....
广度优先遍历（BFS） BFS(Breadth-First-Search)，参考对树的层序遍历
对上面的图从①出发进行BFS得到序列：
①②⑤ ⑥ ③⑦ ④⑧
若采用不同的储存结构，可能会得到不同的遍历结果（这个差异主要来自寻找邻接点的过程），对于邻接矩阵存储的图，由于邻接矩阵是唯一的，所以BFS序列也是唯一的；同理，邻接表存储的图BFS序列不唯一。
BFS算法 与树的层序遍历不同的是，由于图中存在回路，遍历过程中会出现重复访问的问题，故可构造visited数组，用来标记已访问过的数组。
此外，还应针对非连通图做额外的判断，遍历完一个连通分量（极大连通子图）后，遍历查找visited数组中是否还存在未遍历的，如果有即为另一连通分量，继续调用BFS即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 void BFS(Graph G,int v); bool visited[MAX_VERTEX_NUM]; SqQueue Q;//辅助队列 void BFSTraverse(Graph G){ //初始化visited数组 for (int i = 0; i < G.vexnum; ++i) {//使下标从1开始 visited[i]=false; } //对非连通图的处理 for (int v = 0; v < G....
邻接矩阵 Vextex/Vertices 顶点; Martix 矩阵; Arc 弧.
代码实现 1 2 3 4 5 6 7 8 #define MaxVextexNum 100//容许存储的最大顶点数 typedef struct{ char Vex[MaxVextexNum]; //可以将定点之间的关系用int 类型01表示，也可定义为boolean/枚举类型，占空间更小 bool Edge[MaxVextexNum][MaxVextexNum]; int vexnum,arcnum;//顶点数和弧|边数 }MGraph; 即找度 根据邻接矩阵计算结点的度TD
无向图 有向图 $TD(V_i)$ 第i行（或i列）中非零元素的个数 $ID(V_i)$ : i行非零元素个数
$OD(V_i)$: i列非零元素个数
TD=ID+OD 对于带权图（网） 1 2 3 4 5 6 7 8 9 10 11 #define MaxVextexNum 100//容许存储的最大顶点数 #define INIFINITY //宏定义，表示无穷 typedef char VextexType;//顶点 typedef int EdgeType;//权值 typedef struct{ VextexType Vex[MaxVextexNum]; EdgeType Edge[MaxVextexNum][MaxVextexNum]; int vexnum,arcnum; }MGraph; 复杂度 空间复杂度来自数组Vex[]跟Edge[]，故空间复杂度为$|V|+|V|^2=O(|V|^2)$，即为顶点数量的二次方，故此方法更适合存储稠密图，不然有较多浪费。...
平衡二叉树是Adelson-Velsky和 Landis发明，故命名为AVL树。也称平衡二叉查找树。
✨特点： ①左子树<根<右子树； ②任一节点，左右子树高度之差不超过1.
平衡因子 $平衡因子=左子树高-右子树高$
AVL树的插入操作 AVL树插入新结点导致不平衡之后，只需将最小不平衡子树平衡，其他祖先结点会随之恢复平衡。
调整最小不平衡子树 注意：调整过后必须保证其BST的特性，即“左子树1.LL 即在以A为根节点的树的左孩子B的左子树上插入新结点，导致A成为最小不平衡子树。
调整过程如下：
2.RR 即在以A为根节点的树的右孩子B的右子树上插入新结点，导致A成为最小不平衡子树。
调整过程如下：
3.LR 即在以A为根节点的树的左孩子B的右子树上插入新结点，导致A成为最小不平衡子树。
观察得知，所进行的调整就是保证$|平衡因子|<=1$，因此若插入操作使得
左 - 右 > 1 => 右旋
右 - 左 > 1 =>左旋
而当进行了LR插入操作之后，导致以A为根节点的树 左-右>1，理应右旋但是，由上述结果可知，经过右旋之后：
可以看到，为了保证其左子树<根<右子树的特性，经过调整后，依然存在右-左>1的问题；
因此，对于LR型不能简单进行右旋调整，应该先将其转化为LL型 (左旋)，再进行右旋；
为此，我们需要将BR结点展开，之后旋转成为LL型插入
可以看到，展开后又出现两种插入情况CL&CR，但其实两者处理大同小异：
CR插入调整过程如下：
4.RL 即在以A为根节点的树的右孩子B的左子树上插入新结点，导致A成为最小不平衡子树。
参考LR型，其调整过程如下：
查找操作效率分析 Assuming that, $n_h$表示深度为h的平衡树中含有的最少结点，则
$n_0=0$,$n_1=1$,$n_2=2$…存在递归关系 $n_h=n_{h-1}+n_{h-2}+1$,即左右子树结点之和+根节点。
可以证明(AVL证明)，n个结点的平衡二叉树最大深度数量级为$\log_2n$，则其查找操作的复杂度为$O(\log_2n)$