hex*_*ium 3 algorithm big-o graph depth-first-search
感谢大家回复想法和替代解决方案.总是欢迎更有效的解决问题的方法,以及提醒我质疑我的假设.也就是说,我希望你暂时忽略我试图通过算法解决的问题,并且只是帮助我分析我编写的算法的大复杂性 - 一个简单的路径在曲线图使用深度限制搜索所描述这里,和实施这里.谢谢!
编辑:这是作业,但我已经提交了这个作业,我只想知道我的答案是否正确.当涉及递归时,我对Big-O的复杂性感到有些困惑.
原始问题如下:
我试图找到这个算法给出的全路径搜索的复杂性.给定两个顶点,我使用深度优先搜索找到它们之间的所有简单路径.
我知道DFS的时间复杂度是O(V + E),它的空间复杂度是O(V),我的直觉是全路径搜索的复杂性将超过这个,但我无法确定它将是什么.
更新(回应下面的评论):
我正在努力解决凯文培根的六度问题.这通常需要找到一对演员之间的最低分离度,但我必须找到所有分离度(目前,小于6,但这可能会改变).
最糟糕的情况是(我认为)n个顶点上的完整图形.这张图有n!简单路径,对于每个路径,您的算法至少执行n ^ 2个计算步骤 - 对于与路径中最后一个相邻的每个顶点,它对先前访问过的节点的链接列表进行线性扫描.(这不计算搜索的所有中间阶段.)因此复杂性至少为O(n ^ 2*n!),可能更糟.
您尝试解决的问题是什么？