我开始学习时间复杂度，并查看了一些简单排序的时间复杂度示例。
我想知道我们如何计算图中深度优先搜索的平均时间复杂度|V|=n，|E|=m设开始节点为“u”，结束节点为“v”。
问问题
62940 次
2 回答
29
DFS 的时间复杂度为 O(n + m)。考虑到我们只访问每个节点一次，并且在树（无循环）的情况下，我们穿越所有边一次，我们得到了这种复杂性。
例如，如果起始节点是 u，结束节点是 v，我们会考虑最坏的情况，即 v 将是最后访问的节点。所以我们开始访问 u 的第一个邻居的连通分量，然后是第二个邻居的连通分量，依此类推，直到最后一个邻居的连通分量，我们找到 v。我们只访问了每个节点一次，并且没有交叉同一边不止一次。
于 2012-04-12T06:45:39.137 回答
22
如果图以邻接表的形式给出，它将是 O(n+m)，但如果图是邻接矩阵的形式，那么复杂度是 O(n*n)，因为我们必须遍历整个排直到我们找到一条边。
于 2013-05-17T17:28:03.667 回答