文章目录
语法
时间、空间复杂度
加法规则：多项相加，保留最高阶项，并将系数化为1
乘法规则：多项相乘都保留，并将系数化为1
加法乘法混合规则：先小括号再乘法规则最后加法规则
时间复杂度估算看最内层循环，如若没有循环和递归则为O（1）
渐进符号
递归式时间复杂度
递归算法的时间复杂度：
递归的次数 × 每次递归的时间复杂度（适用于每次递归时间复杂度不变的情况）
如果每次递归的时间复杂度随着n变化而变化则要根据代码来观察
线性表
栈
栈是一种先进后出（后进先出）的线性结构，只能在栈的一端（栈顶）进行插入和删除。
递归使用栈
队列
基础队列
循环队列
队列的链式存储
- 入队列和出队列操作都不需要遍历链表
双端队列
串
- 子串 ： 连续的
字符串是线性结构，空格也是字符串
字串是指由主串中任意长度连续的字符构成的序列
例如：
主串：abc
字串：a、b、c、ab、bc
ac不是字串，因为它不是主串中连续的字符
串的模式匹配
朴素模式匹配：
数组
- 注意下标 ！！ 和行列表示
矩阵
直接带数 就完事了
树
- 树种的节点总数 === 数中所有节点的度数之和
+ 1 - 度数为m的树 中第i层上至多有mi-1 个结点 (i >= 1）
- 性质三最多 就是使得每一层拥有尽可能多的节点 性质3取log 就可以得到
h
二叉树概念
二叉树存储结构
二叉树遍历
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层序遍历：从上到下、从左往右依次遍历
通过序列构造二叉树必须有中序序列
平衡二叉树与二叉排序树
最优二叉树（哈夫曼树）
- 主要考构造
- 构造 每次取权重最小的俩个节点
- 最优二叉树构造规则 ：① 总节点数 == 2n - 1 (n为T中元素的个数)② 只有度数为2、0 的节点 没有度数为1的节点
- 5,24,8 17,34,4,13
图的概念
无向图：连接顶点的边是无向边
有向图：连接顶点的边是有向边（弧）
邻接矩阵和邻接表
邻接矩阵：
邻接矩阵更适合存储稠密图（边数很多的图）
完全图（每个顶点都和剩余的顶点有一条边）更适合采用邻接矩阵存储
无向图邻接矩阵：非零元素个数为2e（e为边数）
无向图的邻接矩阵是对称矩阵
A[i][j]=1表示顶点i和顶点j之间有一条无向边
A[i][j]=0表示顶点i和顶点j之间没有边
对于无向图，顶点i的度等于邻接矩阵第i行（列）中非零元素个数
有向图邻接矩阵：非零元素个数为e（e为边数）
有向图的邻接矩阵不一定是对称矩阵
A[i][j]=1表示顶点i和顶点j之间有一条有向边
A[i][j]=0表示顶点i和顶点j之间没有边
对于有向图，顶点i的出度等于第i行非零元素个数，入度等于第i列非零元素个数，顶点i的度=顶点i的出度+入度
邻接表：
邻接表更适合存储稀疏图（边数很少的图）
无向图采用邻接表存储有2e个表结点（e为边数）
有向图采用邻接表存储有n+e个表结点（n为结点数，e为边数）
图的遍历
拓扑序列
查找总结
排序总结
