搞定算法与数据结构(02):拓扑排序的时间复杂度与空间复杂度分析

作者: 王炳明 分类: 算法与数据结构 发布时间: 2021-10-02 21:59 热度:4,055

查看完整目录 –>《搞定算法与数据结构


给定问题

来自:Letcode (210) – 课程表 2

假设给定一个数组,数组的每个元素都是一个长度为2的子数组,表示课堂的依赖关系,比如要学习课程3,比如得先学习课程1,而要学习课程 4,也得先学习课程2,要学习课程5,得先学习课程3和课程4。如下图所示

搞定算法与数据结构(02):拓扑排序的时间复杂度与空间复杂度分析

则数组为:[[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 的都是无解的,都不能使用拓扑排序。

有向:有方向的

无环:不能出现死循环

时间复杂度

拓扑排序 的时间复杂度,是有两个参数的:

  1. 节点数(m):有多少门课程
  2. 边(k):依赖关系数,也即给定数组的长度

从头回顾一下,我们的查找过程

  1. 预处理:需要遍历 k 次,时间复杂度为 O(k)
  2. x轮处理:不管x是多少,反正都是将 m 个课程,依次放次队列中,因此时间复杂度为 O(m)
  3. 整理结果:有了队列后,还是从队列中取出每个节点来,总共有 m 门课程,时间复杂度还为 O(m)

由于时间复杂度是可以直接想加的,因此总的时间复杂度为 O(k+2m),时间复杂度中系数没有意义,因此最终的时间复杂度为:O(k+m)

空间复杂度

在上面的排序中,总共用到了两个数组结构:map 和 queue。

但不管是哪种,他们存放的数据量是固定的 m 个节点,所以空间复杂度是 O(2m),系数同样可以直接去除,最终的空间复杂度是O(m)

参考文章

文章有帮助,请作者喝杯咖啡?

发表评论