如何将BFS中的O(V+E)转换为O(b^d)？

Question

在我的算法分析课程中，老师教我们 Breath First Search 的时间复杂度是 O(V+E)，但现在在人工智能课程中，老师说 BFS 的复杂度是 O(b^d)。当我问他问题时，他给了我一个逻辑理由，即“在理论计算机科学中，O(V+E) 是合适的，因为图是一个明确的数据结构，是输入到搜索算法中的。在人工智能中，图通常由初始状态、动作和转换模型隐含地表示，并且经常是无限的。因此，复杂度用 O(b^d) 表示。”现在我有两个问题：

1. O(V+E) 和 O(b^d) 如何相等，第一个看起来是线性复杂度，第二个是指数复杂度。
2. 当我们谈论大 O 符号时，它意味着无论输入如何，上限都应该保持不变，因为它是一个上限。是否只处理一些有限的数据输入？

来源于维基百科

- Mushahid Hussain

---

请投票关闭的人提供评论，解释为什么他们认为这是离题的？它讨论了一种算法的基础，通常用于解决许多应用程序中的最短路径问题，我认为对于理解它的问题没有任何问题。 - amit

这个问题应该发布在http://cs.stackexchange.com上。 - Peter DeWeese

Answer 1

在人工智能中，通常处理巨大或无限的图形，因此O(V+E)不具有信息量且对这些图形来说并不好用，所以我们尝试获得更好的界限。这个界限是O(B^d)，其中B是分支因子，d是解决方案的深度。背后的理由是，如果您在每个深度上“分支”到B个方向，您最终会探索O(B^d)个节点。

此外，请注意，经典的广度优先搜索算法是一种探索算法，需要探索整个图形（即探索所有顶点），而在人工智能中，我们将其用作路径查找-您探索直到找到从源到目标的路径为止（不需探索整个图形，有时不可能）。

另请注意，如果您查看一棵树（没有任何节点被发现两次），其分支系数为B，所有叶子都位于深度d，则该树中恰好有B + B^2 + B^3 + ... + B^d < B^(d+1)个节点，因此如果您需要...

“O(V+E)和O(b^d)如何相等，第一个看起来像线性复杂度，第二个则是指数级。”

在第一种情况下，图形是输入，因此与输入-图形的大小成正比，具有线性复杂度。 第二个在图形的大小上也是线性的，而在解决方案的深度-不同的因子中呈指数级增长。但仍然不需要多次遍历一个顶点，因此仍然是图形大小的线性复杂度。所以，在这里，基本上O(B^d)是O(V+E)的子集，并且如果您可以容忍您的复杂度是d的函数（不是输入的一部分），则更具信息量。

当我们谈论大O符号时，它意味着无论输入如何，它都应该保持相同的上限，因为它是一个上限。那么，Big O是否仅处理一些有限的数据输入？

如果图形是无限的，大O就没有信息价值，对于每个f(n)，以及每个常数c和N，c*f(n) < infinity，所以在谈论无限图形时是无用的。

- amit

---

谢谢回复，但根据维基百科，O(V+E)等于O(b^d)，我的问题是如何使这两个边界相等？ - Mushahid Hussain

@james：看一下修改，这个想法是-你仍然不需要遍历边缘或顶点超过一次。另外：在无限图的情况下，维基百科是错误的- O(V+E) != O(B^d)。如果 V = infinity，那么 O(V+E) 基本上是 O(infnity)，而 2^(B^d) 也在其中，而它不在 O(B^d) 中。 - amit

@james：还要注意（只是侧面说明），d不是输入的因素。理论算法研究人员倾向于使用大O符号表示法，并且只分析输入的因素，专注于理论方面而非实际方面。AI研究人员对这些限制的束缚较小。 O（B ^ d）可能是您在AI课程中唯一看到的大O表示法，在我的研究和我的教授的研究中 - 我们通常使用其他方法并使用统计工具来检查哪种算法更好。 - amit

你的回答和评论都很有帮助，谢谢。但是为什么这个问题有三个关闭投票呢？ - Mushahid Hussain