TSP 的大 O 时间复杂度
Big O time complexity for TSP
我目前正在阅读这篇文章 - https://core.ac.uk/download/pdf/154419746.pdf 并且对如何计算算法 1 的 O(n^2 * 2^n) 时间复杂度感到困惑。有人可以解释一下吗？本来以为是Bellman-Held-Karp算法，不过好像和普通的伪代码有点区别。
完整的算法实际上是O(n^3 * 2^n)。您给出的复杂度是计算 n 个问题所需的复杂度。但是我们可以通过直接查看代码来找出这种复杂性的来源。
我们的第一个循环是这样的：
foreach w in V do
…
end do
这完全是在 n 步中完成的。
我们可以忽略这一点，因为第二个循环要复杂得多（如果您添加两个复杂性，则更复杂的那个会获胜）
有四个嵌套循环，这意味着我们需要乘以单个复杂性。除了一个之外，所有的都是 O(n)：
for i=2,…|V| 很明显，因为我们遍历了 V 减一中的所有元素
foreach w in S 和 foreach u in S：都包含足够的元素以符合 O(n) 的条件（在第一次迭代中 1，然后 2，然后 4，e.t.c。）
最后我们有了 for each subset S of V where the size of S is i 。这是组合数学，但有 2^n 个元素是正确的。
我目前正在阅读这篇文章 - https://core.ac.uk/download/pdf/154419746.pdf 并且对如何计算算法 1 的 O(n^2 * 2^n) 时间复杂度感到困惑。有人可以解释一下吗？本来以为是Bellman-Held-Karp算法，不过好像和普通的伪代码有点区别。
完整的算法实际上是O(n^3 * 2^n)。您给出的复杂度是计算 n 个问题所需的复杂度。但是我们可以通过直接查看代码来找出这种复杂性的来源。 我们的第一个循环是这样的：
foreach w in V do
…
end do
这完全是在 n 步中完成的。
我们可以忽略这一点，因为第二个循环要复杂得多（如果您添加两个复杂性，则更复杂的那个会获胜）
有四个嵌套循环，这意味着我们需要乘以单个复杂性。除了一个之外，所有的都是 O(n)：
for i=2,…|V| 很明显，因为我们遍历了 V 减一中的所有元素
foreach w in S 和 foreach u in S：都包含足够的元素以符合 O(n) 的条件（在第一次迭代中 1，然后 2，然后 4，e.t.c。）
最后我们有了 for each subset S of V where the size of S is i 。这是组合数学，但有 2^n 个元素是正确的。