我试图了解使用 BFS 遍历具有 n 个节点的树(不一定是二叉树)时的时间复杂度。 根据我的理解，它应该是 O(n^2) 因为我的外循环运行了 n 次，即直到队列不为空并且因为树包含 n 个节点。 我的内部 for 循环必须不断将与特定节点关联的子节点添加到队列中。 (每个节点都有一个包含其所有子节点地址的字典) 因此，例如，如果根节点有 n-1 个节点(因此所有这些节点都没有进一步的子节点)，那么时间复杂度不会是 n*(n-1) = O(n^2)。
我的理解对吗？ 有什么办法可以在 O(n) 中完成吗？请解释。
最佳答案
用节点数和边数来描述图算法的复杂性通常更有用。通常 |V|用于表示节点数，|E|来表示边的数量。
在 BFS 中，我们访问每个 |V|节点一次并将其所有邻居添加到队列中。并且，到算法结束时，图中的每条边都被恰好处理了一次。因此我们可以说 BFS 是 O(|V| + |E|)。
在全连接图中，|E| = |V|(|V| - 1)/2。因此，对于完全连接的图，复杂度为 O(|V|^2) 是正确的；然而，O(|V| + |E|) 被认为是对已知稀疏图的更严格分析。
关于c++ - 使用 BFS 了解树遍历的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44233786/