算法

二分查找：已经排序的数组找值。
1）记录数组左下标和右下标
2）找出mid下标对应的数据，比较target与mid下标数据大小

image.png

插入排序：

image.png
image.png

快速排序：

image.png image.png

归并排序：

image.png
image.png image.png image.png

数据处理技术

查找技术
排序技术

四种基本的存储结构
1）顺序存储
2）链式存储
3）索引存储
4）散列存储

时间复杂度 计算时间开销T与问题规模n的关系

image.png image.png

空间复杂度 空间开销(内存开销)与问题规模n之间的关系

对数据的操作--创建、销毁、增删改查

顺序表（顺序存储的方式存储的线性表）
静态分配 即C语言的数组
动态分配 即Array容器 ，内存扩展方案是新开辟一片空间，然后复制内容，释放旧空间

image.png

链表（链式存储的线性表）

image.png

单链表的反转

image.png

栈

image.png

队列

image.png

串
二叉树（二维链表 ） 时间复杂度从n到log2n

image.png
image.png
image.png

深度：从根结点开始，往下。
高度：到叶子结束，“往上。

满二叉树：除尾结点所有节点二叉展开。
完全二叉树：除最深层，其余层完全展开。

image.png
image.png

排序二叉树(二分搜索树)：每个节点的数值比左子树上的每个节点都大，比所有右子树的节点都小。
平衡二叉树：引入平衡因子，防止二叉树成棍子变链表。
AVL:严格平衡二叉树。平衡因子{-1,0,1} 查询更快，db中用的多。
红黑树：近似平衡二叉树，左右子树高度差小于两倍，目的优化旋转效率。添加删除效率更高。 高级语言常用。

image.png

B-Tree

image.png

hash

image.png

graph

image.png

vertice
edge

image.png image.png image.png image.png

深度优先遍历（DFS）：
一头扎到底，再回溯，再扎到底的过程。
每次访问当前节点的第一个邻接点再回溯。

image.png

广度优先遍历（BFS）：

image.png