特性与复杂度总结:数据结构与算法分析

最小生成(支撑)树:

  Prim普里姆算法
不断选择权值最小的边,始终保持一棵生成树,O(n^2),复杂度与边无关,适合稠密图。
  Kruskal克鲁斯卡尔算法
每个顶点自成连通分量,选择最小跨越边,O(e*loge),复杂度与边有关,适合稀疏图。

最短路径树:

  Dijkstra算法
类似于Prim普里姆算法和PFS,贪心原理,按照层次扩展,O(n^2)。

二叉堆:

上滤(插入)、下滤(删除),O(log n)
建堆:自上而下的上滤(蛮力):O(n log n),自下而上的下滤(Floyd):O(n)

图:

DFS:O(n+e),BFS:O(n+e),PFS:O(n^2)

稳定性快速记忆:冒入、并、数排序是稳定的,速、择、尔、排序是不稳定的。
原地排序指排序时只需在原数组处来回移动数组元素。原地排序的算法有:选择排序、插入排序、希尔排序、快速排序与堆排序等;非原地排序算法只有归并排序。归并排序要用一个同等大小的数组作为存储空间,是空间复杂度最高的排序。


一些例题:

前提与规定:二叉树从1开始编号,根节点深度1,空树高度为0。
1.深度是5的二叉树,最多几个节点?__31__
2.完全二叉树其中一个节点,如果没有左孩子,那它必是叶子:__正确__。
3.有124个叶子节点的完全二叉树最多有多少节点?最多有__248__个,可能值为__247__与__248__。
4.有999个节点的完全二叉树,深度为多少?__10__(因为999小于2的10次方且最接近)
5.有n个节点的二叉树,二叉链表存储,则有2n个指针域,只有__n-1__个用于指向节点的孩子,其余__n+1__个指针域为空。
6.任何一个二叉树的叶子节点,在其前、中、后序遍历中的相对顺序:__不改变__。
7.一个非连通无向图,有28条边,至少有多少个节点?__9个__,因为n(n-1)/2为最大边数。

相关内容:
数据结构复习笔记与一些总结:https://www.svip.tech/archives/907
基于比较、渐进最优的排序算法(插入、希尔、选择、堆、冒泡、快速、归并排序实现):https://www.svip.tech/archives/1152
不基于比较、线性时间运行的排序算法(计数、基数、桶排序分析)和顺序、对分查找实现:https://www.svip.tech/archives/1165
各种算法特性与复杂度总结:https://www.svip.tech/archives/1174

发表评论

电子邮件地址不会被公开。 必填项已用*标注