使用回溯的哈密顿循环问题的最坏情况时间复杂度是多少？是O（n！）还是O（n ^ n）？因为我试图找出复杂性并且它出现了O（n×n！），它更像是O（n ^ n），而不是O（n！） .
用于找到哈密顿循环的强力解决方案需要O（n！）工作（实际上是O（n ^ n），但是O（n ^ n）不是紧的上限） .
具有n个节点的图G中的哈密顿循环具有形式H = v_1，v_2，v_3，...，v_n，v_1 .
由于 H 包含 G 中的每个节点，我们可以从任意选择的节点开始搜索，例如v_1 . 随后，有 n-1 个候选节点成为第二个节点 v_2 （即，所有节点，但 v_1 本身）;第三个节点 v_3 有 n-2 个选择（即除了 v_1 和 v_2 的所选候选者之外的所有节点），依此类推;在最后有 v_1 到 v_n-1 的候选人修复时， v_n 还剩下一个候选人 .
H
G
n-1
v_2
v_1
v_3
n-2
v_n-1
v_n
（i）这导致最多（n-1）（n-2）......（2）（1）=（n-1）！组合 . （ii）在一个简单的实施中，检查每个组合需要O（n）工作;即，为了检查给定组合是否是哈密顿循环，我们遍历给定组合的整个序列并确保它具有哈密顿路径的所需属性 .
因此，
整体复杂度为O（n）x（n-1）！ = O（n！）
当然，我们可以使用各种技术减少所需的工作，例如分支和绑定方法 .
1 回答
用于找到哈密顿循环的强力解决方案需要O（n！）工作（实际上是O（n ^ n），但是O（n ^ n）不是紧的上限） .
由于
H包含G中的每个节点，我们可以从任意选择的节点开始搜索，例如v_1 . 随后，有n-1个候选节点成为第二个节点v_2（即，所有节点，但v_1本身）;第三个节点v_3有n-2个选择（即除了v_1和v_2的所选候选者之外的所有节点），依此类推;在最后有v_1到v_n-1的候选人修复时，v_n还剩下一个候选人 .因此，
当然，我们可以使用各种技术减少所需的工作，例如分支和绑定方法 .