如何计算TSP动态规划路径回溯代码中while循环的时间复杂度

核心结论 #

这个get_path函数的时间复杂度为 O(n²)，其中n是TSP问题的节点总数。

复杂度推导过程 #

你担心的「无法提前确定while循环终止时机」其实是误解，这个循环的迭代次数是完全确定的：

• 初始path长度为1（只包含起点），循环终止条件是len(path) == n
• 每次进入while循环体，都会恰好往path中追加1个未访问的节点
• 因此while循环总共只会执行 n-1 次，和权值、DP表内容没有任何关系

接下来看每次循环内的操作：
每次while迭代都会执行一轮遍历所有n个节点的for循环，即使中途找到符合DP转移条件的节点k，你当前的代码没有加break跳出for循环，仍然会跑完剩余所有节点的判断；就算你后续加上break优化，最坏情况也是每次要遍历完所有n个节点才能找到目标k。
因此总操作数的上界为 (n-1)*n，对应时间复杂度O(n²)。

补充说明 #

和前序DP求解最短路径长度的O(n²·2ⁿ)复杂度相比，路径回溯的O(n²)开销极小，完全不会成为整个TSP解法的性能瓶颈。如果要优化这个函数，只需要在找到符合条件的k后加break跳出当前for循环即可，平均运行速度会明显提升，最坏复杂度依然保持O(n²)不变。

内容的提问来源于stack exchange，提问作者K.S Kim