问为什么迭代深化搜索O(bm)的空间复杂性？
EN

Stack Overflow用户

提问于 2020-04-22 08:25:14

回答 1查看 1.3K关注 0票数 0

在人工智能:一种现代方法教科书中，入侵检测系统的空间复杂度为O(bm)，其中b =分支因子，m =树的最大深度。IDS在遍历期间存储哪些节点，使其具有O(bm)空间复杂性？

回答已采纳

发布于 2020-04-22 09:29:07

在维基百科上，它说空间的复杂性仅仅是目标的深度d，因为它本质上是深度优先搜索；这是它在我的AIAMA副本(第88页)中实际说的。

我只能想象O(bm)假设所有访问节点的顶层都被存储，这将是分支级别乘以当前深度。没有必要存储较高级别的节点，因为它们已经被搜索过了.

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/61360503

复制

相似问题

问为什么迭代深化搜索O(bm)的空间复杂性？EN