mablog数据结构
type
status
date
slug
summary
tags
category
icon
password
网址
prim 算法，某顶点到其他边的权值，最小，加入树， 树中顶点到其他边权值最小且不是回路的边， 加入
Kruskal 算法 查找所有权值最小的边且不构成回路
一. 顺序表和链表 带头节点的链表好处，插入只用判断不为空
二。
kmp next 求法
树
结点数= 总度数 + 1
六. 图
最小生成树算法
v3 加入后 更新到V1的权值为5 V2 的 4
此算法适合边稠密图
单源最短路径 BFS dijkstra
每对顶点最短路径 Floyd
prim 和 dijkstra 区别
prim 是顶点间 距离最短
这两个算法在添加新结点时，都是选择“距离最短”的结点加入集合，但是Prim算法中，“距离最短”是指未访问的结点到已经访问的所有结点距离最小，即将已经访问的结点视为一个整体，将距离最小的结点加入到已访问的集合中；而在Dijkstra算法中，“距离最短”是指所有未访问结点（通过已访问的结点）到源点距离最小
Floyd算法 动态规划思想
有向无环图 DAG
拓扑排序
AOE 网
七. 查找
ASL 平均查找长度
顺序查找
AVL 成功 = n+1/2 AVL失败 = n+1
有序 的 AVL失败 = 1+2+ … +n + n/n +1 = n/2 + n/n+1
AVL
每个节点（m-1）个关键字
八. 排序
- 插入排序
- 希尔排序
设定固定增量一般为n/2. 每次排完序后增量减半继续比较， 不稳定
- 冒泡排序
- 快速排序 不稳定
- 选择排序 不稳定
- 堆排序
7.归并排序 稳定， 时间复杂度一直未nlogn
- 基数排序
9.外部排序
败者树
置换选择排序
排到不能排序存不下的时候增加一个归并段继续按顺序输出
最佳归并树 读写次数最少即 哈发满树
/
上一篇
kyziliao
下一篇
计算机网络
Loading...