感谢大家回复想法和替代解决方案。更有效的解决问题的方法总是受欢迎的，也欢迎质疑我的假设。也就是说，我希望你暂时忽略我试图用算法解决的问题，而只是帮助我分析我编写的算法的复杂性——所有简单的路径在图中使用描述的深度有限搜索here，并实施了here。谢谢！
编辑：这是作业，但我已经提交了这份作业，我只是想知道我的答案是否正确。当涉及递归时，我对 Big-O 复杂性感到有点困惑。
原问题如下：
我试图找出全路径搜索的复杂性，如下所示this算法。
给定两个顶点，我使用深度优先搜索找到它们之间的所有简单路径。
我知道DFS的时间复杂度是O(V+E)，空间复杂度是O(V)，我的直觉是全路径搜索的复杂度会不止于此，但我无法确定它会是什么。
相关问题here and here.
更新（回应下面的评论）：
我正在尝试解决凯文·培根的六度问题。这通常需要找到一对演员之间的最低分离度，但我必须找到所有分离度（目前小于 6，但这可以改变）。
最坏的情况是（我认为）完整的图表n顶点。该图有n！简单的路径，对于每个路径，你的算法至少执行n^2 计算步骤——对于路径中与最后一个相邻的每个顶点，它对先前访问过的节点的链表进行线性扫描。 （这还没有计算搜索的所有中间阶段。）所以复杂度至少为 O(n^2 * n！），可能更糟。
您想要解决的更大问题是什么？
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
