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)）。