数据结构期末复习 一小时不一定不挂科（？）系列

时间复杂度：

没有循环或递归的算法，时间复杂度：O(1)

循环n次，O(n)

冒泡排序（两循环嵌套），O(n2)

二分查找（长度为n每次除以2）O(log2 n)

递归计算斐波那契数列，O(2的n次方)

嵌套：总复杂度=两复杂度的乘积；

并列：总复杂度=最大的时间复杂度。

线性表、栈（先进后出）和队列（先进先出）

特定：

树和二叉树

前中后序遍历

根据前中后序画二叉树

哈夫曼树

图

深度、广度优先遍历

最小生成树（找最小连通）

prim算法：从节点出发，找最近点

Kruskal算法：从边出发，找最短边

【注】最后把顺序写出来，不能存在闭环

最短路径（从一个节点到每一个节点的最小路径）

查找

平均查找长度的计算（比较(查找)了几次长度就是几）

二叉排序树的构造和查找（比当前节点的大放到左子树，小放到右子树）

哈希表的构造和查找

线性探查法：从前往后依次找空位

平方探查法：发生冲突先找位序+1，再找位序-1，再找位序+4，-4，+9，-9…以此类推直到找到空位。如果超出首节点时紧接着从首节点往尾节点查找。