图算法的运行时间

Question

我有点困惑如何确定图算法的运行时间。也就是说，使用顶点数（n）和边数（m）来估计运行时间。请问是否有人能够解释我的逻辑错误，并且讲解如何正确地分析这些内容以及找到运行时间？

以下是一个图算法的示例：

//input: Directed graph G represented by adjacency lists.
Func1(G) {
k = 0;
foreach vertex vi in V(G) do
    foreach directed edge (vi, vj) incident on vi do
    k=k+1; //just some constant time operation
    end
end
return(k);
}

该图算法的运行时间以BigO符号表示为O(m+n)。现在我有一个问题：仅仅快速地对该算法进行精神分析，为什么运行时间不是O(n*m)呢？外部循环运行n次，换句话说，每个顶点运行一次。现在内部循环运行m次，即每条边运行一次。因此，我认为两个循环加起来将运行n*m次。

最后一个不那么简单的问题是，如果输入以邻接矩阵而不是邻接列表的形式给出，算法的运行时间会如何改变？

我在网上找不到好的资源来解决这个问题，没有明确简明的例子涵盖这个主题。如果有人能帮我创建一个，我会非常感激 :)

- Musicode

Answer 1

该算法对于每个与vi相邻的边仅运行一次。由于每条边与2个顶点相邻，因此最终每条边被访问两次，每个顶点被访问一次。因此，使用邻接表O(n+2m) = O(n+m)。

使用邻接矩阵查找与vi相邻的边需要O(n)次操作。因此，该算法的时间复杂度为O(n²)。

- Juan Lopes

---

这难道不意味着运行时间只是2m吗？在这种情况下，n是如何发挥作用的--毕竟，在外循环中除了内循环没有其他操作。 - Musicode

不考虑任何边的情况下，假设有n个顶点的图。运行时间仍然是O(n)。在实践中，O(n+m)意味着O(max(n, m))。 - Juan Lopes

所以我从中学到的是，我们需要考虑算法总共访问每条边/顶点的次数。谢谢。 - Musicode

@Musicode：通常在这样的循环中，计算不同变量绑定集合的数量是个好主意，然后证明每个值组合仅出现了固定次数。在这种情况下，每对变量（vi，vj）的值都对应于图中的一条边，而且您只访问每条边两次。 - Niklas B.