5

在我的算法分析课程中，老师告诉我们呼吸优先搜索的时间复杂度是 O(V+E)，但现在在人工智能课程中老师说 BFS 的复杂度是 O(b d )。当我问他问题时，他给了我一个合乎逻辑的理由，即“在理论计算机科学中，O(V+E) 是合适的，因为图是输入到搜索算法的显式数据结构。在 AI 中，图通常表示由初始状态、动作和过渡模型隐含地表示，并且通常是无限的。因此，复杂度用 O(b d )" 表示。现在我有两个问题

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

4

1 回答 1

10

在人工智能中 - 您通常处理巨大/无限图，因此对于这些图来说O(V+E)信息量不足且不够好，因此我们试图获得更好的界限。这个界限是O(B^d)，其中B是分支因子，d是解的深度。这背后的原因是，如果你在每个深度“分支”到 B 方向，你最终会探索O(B^d)节点。

此外 - 请注意，您的算法课程中的经典 BFS 是探索算法- 它需要探索整个图（探索所有顶点），而在 AI 中我们将其用作寻路- 您一直探索直到我们找到从源到目标的路径. （没必要，有时不可能探索整个图）

另请注意，如果您查看一棵树（没有发现两次节点），具有分支因子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 是否只处理一些有限的数据输入？

如果图是无限的，那么对于每个 f(n) 和每个常数 c,N - ，大 O 都不能提供信息，c*f(n) < infinity因此在谈论无限图时它是无用的。

于 2012-10-10T13:10:08.117 回答