算法图解笔记
算法图解笔记
1.2.2 运行时间
线性时间：$O(n)$。需要查找的次数与列表长度相同。
对数时间：$O(\log n)$。例如：二分查找的运行时间。
$\log n$ 表示 $\log_2 n$
1.3 大 O 表示法
- 指出了算法运行时间的增速，即运行时间如何随列表增长而增加。
- 指出了最糟糕情况下的运行时间
5.4.1 填装因子
\(填装因子 = \frac{散列表包含的元素数}{位置总数}\)
填装因子越低，发声冲突的可能性越小，散列表的性能越高。
一个经验规则是：一旦填装因子大于 0.7，就调整散列表的长度。
6.2 图是什么
由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。
6.3 广度优先搜索
广度优先搜索是一种用于图的查找算法。
可以帮助回答两类问题：
- 从节点 A 出发，有前往 B 节点的路径吗？
- 从节点 A 出发，前往节点 B 的哪条路径最短？
6.3.2 队列
类似排队上车。先排队的先上车。
6.4 实现图
有向图：单向箭头。箭头的方向指定了关系的方向
无向图：没有箭头，直接相连
6.5 实现算法
广度优先搜索的运行时间为 $O(V + E)$。
V：顶点数
E：边数
拓扑排序：如果任务 A 依赖于任务 B，在列表中任务 A 就必须在任务 B 的后面。可以根据图创建一个有序列表。
树是一种特殊的图。
第七章 狄克斯特拉算法（Dijkstra’s algorithm）
广度优先搜索可以找出最短路劲。该算法可以找出最快路劲（用时最少）。
7.2 术语
权重(weight)：每条边有关联的数字
加权图(weighted graph)：带权重的图
非加权图(unweighted graph)：不带权重的图
计算非加权图中的最短路劲可使用广度优先搜索。要计算加权图中的最短路径可以使用狄克斯特拉算法。
环：从一个节点出发，走一圈后又回到这个节点。
无向图意味着两个节点彼此指向对方，其实就是环。
在无向图中，每条边其实就是一个环。
狄克斯特拉算法只适用有向无环图(directed acyclic graph，DAG)。
不能将狄克斯特拉算法用于包含负权边的图。