algorithm - 您如何估计该算法的时间复杂度？

Question

设 N=顶点数 M=边数有向图 G 的图。我们以邻接表的形式存储边。为了清楚起见，我们假设 Oi 是顶点 i 的出度，Ii 是顶点 i 的入度。

算法如下:

for each vertex i
  for each vertex j in i's adj.list
    //do some work
    for each vertex k in j's adj.list
      //do some work

“做一些工作”本质上是在恒定时间 (O(1)) 内完成的。我无法推导出 N、M 中运行时间的一般表达式。有人可以解释如何做到这一点吗？

顺便说一句:为了防止出现“我不会做你的作业”的评论，我正在练习 CLRS 的文本问题(这是 22.1-5)。我这样做是为了学习如何估计图算法的时间复杂度。

Answer 1

我假设算法中提到的每个邻接列表都是一个出边列表。相反，如果传入和传出边都被引用，则总工作量将乘以常数因子 4，而不会影响 O() 级别。

将 for 语句称为 F1、F2、F3，我们有 F1 循环 N 次。 F2 总共循环 O1+O2+... = M 次，其中 Oi 是问题中提到的出边度数。 F3 每次 F2 循环至多循环 N 次，最坏情况的下限不会比这小。这导致算法的时间为 O(M·N)(即，F1 和 F2 的 O(M)，每个 F3 的 O(N))。