十、 图论
-
基本概念/术语
-
顶点/节点（Vertex/Node），简称点。
-
边（Edge）：节点之间的连线。
-
完全图：任意两点都有边相连，一个 n 个节点完全图的边数 C2n=n(n−1)2 。（对于组合数 C2n 的具体说明详见“数学”部分）
-
简单路径：两点之间通过不重复的边相连。
-
连通图：任意两点都可以直接/间接到达，注意区别于完全图，完全图属于连通图，连通图不一定属于完全图。
-
有向图：边是有方向的（ e=u→v ）。
-
无向图：边是无方向的（ e=u↔v ）。
-
环：对于一个回路 w ，若 v0=vk 是该回路点序列中唯一重复出现的点对，则 w 是一个环。
特别的，如果环 w 只有一个点，则被称为“自环，即 e=(u,v),u=v 。
-
入度：以顶点 v 为终点的边的条数为该节点的入度。
-
出度：以顶点 v 为起点的边的条数为该节点的出度。
-
-
树
-
基本概念/术语
- 树：一个长得像真实生活中 倒置（即根在上、叶子在下） 的树的图，任意两点之间的简单路径有且只有一条。树是一棵连通且无环的图，边数 =n−1 。
- 根节点：树最上层的节点，一棵树有且只有一个。
- 深度：到根结点的路径上的边数。
- 高度：所有结点的深度的最大值。
- 叶节点：没有子结点的结点。
- 父亲：对于除根以外的每个结点，从该结点到根路径上的第二个结点。根结点没有父结点。
- 祖先：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。
- 子节点：如果 u 是 v 的父亲，那么 v 是 u 的子结点。子结点的顺序一般不加以区分，二叉树是一个例外，有左儿子/右儿子之分。
- 兄弟：同一个父亲的多个子结点互为兄弟。
- 后代：如果 u 是 v 的祖先，那么 v 是 u 的后代。
- 子树：删掉与父亲相连的边后，该结点所在的子图。
-
二叉树
-
前/先序遍历：根 → 左子树/儿子 → 右子树/儿子。
-
中序遍历：左子树/儿子 → 根 → 右子树/儿子。
-
后序遍历：左子树/儿子 → 右子树/儿子 → 根。
-
遍历的特殊结论
- 前/先序遍历 + 中序遍历 = 确定二叉树。
- 后序遍历 + 中序遍历 = 确定二叉树。
-
特殊的二叉树及其性质
- 满二叉树/完美二叉树：所有叶结点的深度均相同的二叉树称为满二叉树/完美二叉树。
满二叉树的第 k 层有 2k−1 个节点，任意 k 层二叉树最多有 2k−1 个节点。
若在任意一棵满二叉树中，有 n0 个叶子节点，有 n2 个度为 2 的节点，则有 。
n 个节点的满二叉树深为 logn+1
- 完全二叉树：只有最下面两层结点的度数可以小于 ，且最下面一层的结点都集中在该层的最左侧。
- 对于一棵满二叉树/完美二叉树，其深度为 k ，则其节点总数为 2k−1 ，此结论可逆。
- 对于一棵满二叉树/完美二叉树/完全二叉树，若任意节点（除叶节点外）的编号为 i ，其左儿子的编号为 2i ，右儿子的编号为 2i+1 。此结论可逆，证明显然。
二叉树的第 k 层至多有 2i−1（i≥1） 个节点。
-
-
-
习题
-
栈
-
定义/术语
-
定义：有一叠碗，每一次取的时候取最上面的出来，放的时候放到最上面，先进来的后出去，后进来的先出去，这就是后进先出（last in first out）表，简称 LIFO 表。
-
栈顶：栈最顶端的元素。
-
栈底：栈最底端的元素。
-
-
操作
push(x)往栈顶前添加一个元素 。pop()从栈顶弹出（删除）一个元素。top()返回栈顶的值。empty()返回是否为空。（1 为空， 为非空）size()返回栈里的元素个数。
-
-
队列
-
定义/术语
-
定义： 与生活中的队列相同，一条队伍，没有人会插队，大家都按队伍的规矩排好。先进来的先出去，后进来的后出去，这就是先进先出（first in first out）表，简称 FIFO 表。
-
队首/队头：队列的第一项。
-
队尾：队列的最后一项。
-
操作
-
push(x)往队尾后添加一个元素 x 。 -
pop()从队首弹出（删除）一个元素。 -
front()返回队首的值。 -
empty()返回是否为空。（ 1 为空 0 为非空 ） -
size()返回队列里的元素个数。
-
-
-
链表
-
定义/特点
- 定义：链表和数组都可用于存储数据，其中链表通过指针来连接元素，而数组则是把所有元素按次序依次存储。
- 链表可以方便地删除、插入数据，操作次数是 O(1) ，但是访问任意数据时操作次数是 O(n) 。
- 链表不可以随机访问任意数据！
-
习题
-
-
字符串
-
定义：字符串指一串字符组成的串。
-
子串：子串被定义为字符串中任意个连续的字符组成的子序列，子串个数 =n(n+1)2+1 ，非空子串的个数 =n(n+1)2 （无非就是少了空子串的 +1 ）
-
前/中/后缀表达式：
-
前缀表达式：一种没有括号的表达式，与中缀表达式不同的是，将运算符写在前面，操作数写在后面。如：前缀表达式 −1+23 的中缀形式为 1−(2+3) 。
-
中缀表达式：与平常使用的表达式相同，有括号且运算符在操作数中间。
-
后缀表达式：与前缀表达式相反，将操作数写在前面，运算符写在后面。如：后缀表达式 123+− 的中缀形式为 1−(2+3) 。
-
前/中/后缀表达式的转化
-
前/后缀表达式转中缀表达式
- 画出表达式树：表达式树是一种特殊的树，叶节点是操作数，其他节点为运算符
- 将表达式树前序遍历，可得前缀表达式；中序遍历可得中缀表达式；后序遍历可得后缀表达式。
-
中缀表达式转前/后缀表达式
-
给中缀表达式加上括号：
1−2+3→((1−2)+3)
-
把运算符移到括号前/后面（移到前面为前缀表达式，反之亦然）：
(1−(2+3))→((12)−3)+
-
删去括号，剩下的即为最终解：
(1(23)+)−→12−3+
也可以用上文的“表达式树”做，比较复杂，推荐以上加括号的方法。
-
-
-
-
十一、排列组合
-
加法原理：完成一项工作有 n 种方法， ai(1≤i≤n) 代表完成第 i 类方法的数目，共有 S=a1+a2+⋯+an−1+an 种不同的方法。
-
乘法原理：完成一项工作有 n 个步骤， ai(1≤i≤n) 代表完成第 i 个步骤的数目，共有 S=a1×a2×⋯×an−1×an 种不同的方法。
-
排列（Arrangement/Permutation）
-
定义：从 n 个不同元素中，任取 m （ m≤n ）个元素按照一定的顺序排成一列，读做从 n 个不同元素中取出 m 个元素的一个排列，记为 Amn （或 Pmn ）。
-
计算公式： Amn=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!
其中， ! 表示阶乘，例如 6!=1×2×3×4×5×6 ，特别规定 0!=1。
-
证明：第 1 个位置可以选 n 个元素，第 2 个位置由于先前已经选了一个，还可以选 (n−1) 个元素，以此类推，第 m 个可以选 (n−m+1) 个元素。又根据上述的乘法原理，将所有的选法串联起来，因此得到上式。
-
全排列：排列的一种特殊情况，此时 m=n,n−m=0 ，刚刚规定过 0!=1 ，所以 Ann=n!=1×2×3⋯×n 。
-
-
组合（Combination）
- 定义：从 n 个不同元素中，任取 m(m≤n) 个元素组成一个集合，读做从 n 个不同元素中取出 m 个元素的组合。即不关心被选元素的顺序。记为 Cmn 。
- 公式： Cmn=Amnm!=n!m!(n−m)!
- 证明：如果 n 个元素中选 m 个且关心顺序，为 Amn 。但是此时不关心顺序了，就需要去掉重复的，同样选出来的 m 个元素，还要进行全排列，即除掉 m! ，因此展开后得到上式。
组合数也常用 (nm) 表示，读作“ n 选 m ”，更为清晰明了。
-
排列组合九大解题技巧（按个人认为的理解难度排序）
-
先选后排：先将元素选出来，再进行排列，非常有效的降低问题的复杂度。
-
特殊优先：特殊元素，优先处理；特殊位置，优先考虑。
-
分排用直排： n 个元素，从中选出 m 个，将这 m 个元素排成若干排。分排问题的排列可以看做一排，避免考虑了复杂的前后排列，简化了问题。
S=Amn
-
分类法：当计算符合条件的数目比计算不符合条件数目简单时，将问题分成若干类，逐个求解，与“排除法”相对。
-
排除法：当计算符合条件的数目比计算不符合条件数目复杂时，简称正难则反。排除不符合要求的，剩下的就是符合题目要求的。与“分类法”相对。
-
捆绑法： n 个不同元素排成一列，要求 m 个元素必须相邻。可以特殊优先，把 m 个元素捆绑在一块单独处理。
S=An−m+1n−m+1×Amm
-
插空法： n 个不同元素排成一列，要求 m 个元素不能相邻。先把不用特殊处理的元素进行排列，再把甲乙进行插空。
S=An−mn−m×Amn−1
-
隔板法/插板法：将 n 个相同元素分成 m 组，每组至少有一个元素。相当于把 m−1 个隔板插到 n 个元素形成的 n−1 个空隙里。
S=Cm−1n−1
-
定序： n 个元素的全排列中有 m 个元素必须定序排列，这 m 个元素相邻或不相邻不受限制。
S=AnnAmm
-
-
习题
-
十二、复杂度
一个问题有很多种不同的算法，如何评价一个算法的好坏呢？这就需要时间复杂度和空间复杂度来衡量了。
-
定义
渐进时间复杂度，用符号 O 表示。一个算法里语句的执行次数可以用一个式子表示，取这个式子的最高次项且忽略系数表示该算法的时间复杂度。例如，一个程序的语句执行次数为 2n+3n2+9+8n ，则该算法的时间复杂度为 O(n2) 。
-
常量
常量，即永远不变的量，例如， 1 就是 1 ，它永远不可能等于 2 。在时间复杂度里，只要不随着输入数据规模的大小增长而增长的量，就被称之为常量，在计算中省去不写。
特别的，如果代码中出现了宏定义，那么宏定义的值依旧是常量，因为它不随着输入数据规模的大小而改变。
-
示例
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j];本代码中，
cin >> a[i][j]执行了 n2 次，所以时间复杂度为 O(n2) 。for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> b[i][j];本代码中，
cin >> a[i][j]执行了 n2 次，cin >> b[i][j]也执行了 n2 次，忽略系数，时间复杂度还是 O(n2) 。for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin >> a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) cin >> b[i][j];本代码中，
cin >> a[i][j]执行了 n2 次，cin >> b[i][j]执行了 n3 次，取最高次项，时间复杂度是 O(n3) 。 -
符号
T(n) 表示时间复杂度， T(n)= 后跟一个符号：
Θ ，
theta，等于。O （也可写作 O ），
big-oh，小于等于。Ω ，
big-omega大于等于。o ，
small-oh小于。ω ，
small_omega大于。 -
非递归程序的时间复杂度的计算
非递归程序的时间复杂度计算一般都比较简单，直接数循环。大多数算法都适用于此，但是也有例外，例如二分等，需要特别留心。
-
递归程序&主定理
假设某算法的计算时间表示为递归式：
T(n)=2T(n2)+nlogn
T(1)=1
求该算法的时间复杂度。
- 直接代入递归求解
1.T(n)=2T(n2)+nlogn
=4T(n4)+2×n2logn2+nlogn
=8T(n8)+nlogn4+nlogn2+nlogn
=…
T(n)=logn∑i=0nlogn2i
=nlogn∑i=0logn2i
=nlogn∑i=0log2i
=nlogn∑i=0i
=Θ(nlog2n)
2.T(n)=T(n/2)+nlogn
=T(n/4)+n2logn2+nlogn
=nlogn+n2logn2+n4logn4+n8logn8+…
上式≥nlogn
上式≤nlogn+n2logn+n4logn+n8logn+…=2nlogn
∴=Θ(2nlogn)=O(nlogn)
虽然此方法计算量较大，但是是初学者不二的选择。如果追求卷面，可以学习主定理。
- 主定理：将一个规模为 n 的问题，分治成 a 个 ⌈nb⌉ 的子问题，每次带来的额外计算为 O(nd) ，可得到以下关系式：
T(n)=aT(⌈nb⌉)+O(nd)
(for constants a>0,b>1,d≥0),then:
T(n)=⎧⎪⎨⎪⎩O(nd)ifdgt;logbaO(ndlogn)ifd=logbaO(nlogba)ifdlt;logba
-
空间复杂度
-
定义：空间复杂度较时间复杂度来说简单许多，可以直接数。符号同时间复杂度。
-
计算
[Math Processing Error]
可见，只需要数数组有几维即可，其他注意事项（如常数等）与时间复杂度相同。
-
排序算法
初赛里常考的的排序大多分为 8 种：选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序、基数排序。
[Math Processing Error]
基于比较：通过比较元素来排序数列，如冒泡排序，快速排序等。
不基于比较：不比较元素，通过其他方法（如hash）来进行排序，如基数排序等。
完结撒花(￣▽￣)
(有问题的话请大佬告知我)
第十章后边大部分内容参照洛谷文中图片全是网上的
©2024本内容版权归 梅耀元 所有，未经授权请勿转载。
0 条评论
