你好,我是黄申,今天我们接着聊复杂度分析的实战。
上一讲,我从数学的角度出发,结合自身经验给你总结了几个分析复杂度的法则。但是在实际工作中我们会碰到很多复杂的问题,这个时候,正确地运用这些法则并不是件容易的事。今天,我就结合几个案例,教你一步步使用这几个法则。
案例分析一:广度优先搜索
在有关图遍历的专栏中,我介绍了单向广度优先和双向广度优先搜索。当时我提到了通常情况下,双向广度优先搜索性能更好。那么,我们应该如何从理论上分析,谁的效率更高呢?
首先我们来看单向广度优先搜索。我们先快速回顾一下搜索的主要步骤。
第一步,判断边界条件,时间和空间复杂度都是 O(1)。
第二步,生成空的队列。常量级的 CPU 和内存操作,根据主次分明法则,时间和空间复杂度都是 O(1)。
第三步,把搜索的起始结点放入队列 queue 和已访问结点的哈希集合 visited,类似上一步,常量级操作,时间和空间复杂度都是 O(1)。
第四步,也是最核心的步骤,包括了 while 和 for 的两个循环嵌套。
我们首先看时间复杂度。根据四则运算法则,时间复杂度是两个循环的次数相乘。对于嵌套在内的 for 循环,这个次数很好理解,和每个结点的直接连接点有关。如果要计算平均复杂度,我们就取直接连接点的平均数量,假设它为 m。