在我的算法分析课程中，老师教我们广度优先搜索的时间复杂度是O(V+E)，但现在在人工智能课程中，老师说BFS的复杂度是O(bd)。当我问他这个问题时，他给出了一个合理的解释，即“在理论计算机科学中，O(V+E)是合适的，因为图是一个显式的数据结构，是搜索算法的输入。在AI中，图通常由初始状态、动作和转换模型隐式表示，并且经常是无限的。因此，复杂度以O(bd)的形式表达。”现在我有两个问题
- O(V+E)和O(bd)如何相等？前者看起来是线性复杂度，而后者是指数复杂度。
- 当我们谈论大O表示法时，它意味着无论输入如何，上限都应该保持不变，因为它是一个上限。大O表示法是否只处理有限数据输入？
回答：
在人工智能中 – 你通常处理的是巨大/无限的图，因此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的函数，而d不是输入的一部分。
当我们谈论大O表示法时，它意味着无论输入如何，上限都应该保持不变，因为它是一个上限。大O表示法是否只处理有限数据输入？
如果图是无限的，大O表示法没有信息量，对于每个f(n)，以及每个常数c,N – c*f(n) < 无穷大，所以在谈论无限图时是无用的。
