搞定算法与数据结构(02):拓扑排序的时间复杂度与空间复杂度分析
查看完整目录 –>《搞定算法与数据结构》
给定问题
假设给定一个数组,数组的每个元素都是一个长度为2的子数组,表示课堂的依赖关系,比如要学习课程3,比如得先学习课程1,而要学习课程 4,也得先学习课程2,要学习课程5,得先学习课程3和课程4。如下图所示
则数组为:[[3,1], [4,2], [5,3], [5,4]]
那么问题来了,如何找到一条学习路径,可以学习完所有的课程。
上例是为了方便我理解问题,所以课程数比较少,依赖关系也比较简单,所以从图中可以一眼看出来:1,2,3,4,5
而在实际问题中,课程数会非常多,依赖关系也会更加复杂,此时你就很难画图直观说出一条准确的学习路径了。
排序逻辑
虽然没法画图了,但可以从上图中总结出一些规律,来方便我们编码实现查找过程。
我们回想一下,为什么最开始我们会盯上 1 和 2 ,先学他们呢?
还不是他们的入度为 0,入度为0 的节点,我暂且将他们称之为可执行节点
入度:顶点的入度是指「指向该顶点的边」的数量;
出度:顶点的出度是指该顶点指向其他点的边的数量。
预处理
准备一个 map,遍历一遍数组,记录下每个入度的课程信息。
{
0: [1, 2],
1: [3, 4],
2: [5]
}
我们只需要准备一个队列,把那些入度为0 的节点先放入队列中。
第一轮
把这些可执行节点(课程1 和课程2)放入队列中后,那依赖这些可执行节点的节点(课程3 和课程4)的入度要相应的减掉 1。
第二轮
检查上一轮入度有更新的节点(课程3 和课程4)的入度是否为 0 ,若为 0,则也将其放入队列中,放入完成后,依赖本轮的可执行节点的节点(课程5)入度减去1。
第三轮
检查上一轮入度有更新的节点(课程5)的入度是否为 0 ,由于5最初的入度为2,经过第二轮后,入度减掉了2,目前的入度为0,因此将其最后放入队列中。
最终结果
从队列中分别取出,即是可行的一条学习路径。
这种排序方法,就是大名鼎鼎的 拓扑排序 (Topological Order)。
拓扑排序的基础是给定的数组,能够描绘出 有向无环图 (Directed Acyclic Graph,简称DAG),不是 DAG 的都是无解的,都不能使用拓扑排序。
有向:有方向的
无环:不能出现死循环
时间复杂度
拓扑排序 的时间复杂度,是有两个参数的:
- 节点数(m):有多少门课程
- 边(k):依赖关系数,也即给定数组的长度
从头回顾一下,我们的查找过程
- 预处理:需要遍历 k 次,时间复杂度为 O(k)
- x轮处理:不管x是多少,反正都是将 m 个课程,依次放次队列中,因此时间复杂度为 O(m)
- 整理结果:有了队列后,还是从队列中取出每个节点来,总共有 m 门课程,时间复杂度还为 O(m)
由于时间复杂度是可以直接想加的,因此总的时间复杂度为 O(k+2m),时间复杂度中系数没有意义,因此最终的时间复杂度为:O(k+m)
空间复杂度
在上面的排序中,总共用到了两个数组结构:map 和 queue。
但不管是哪种,他们存放的数据量是固定的 m 个节点,所以空间复杂度是 O(2m),系数同样可以直接去除,最终的空间复杂度是O(m)
参考文章: