python - 2 opt swap算法复杂度

Question

def two_opt(route):
 best = route
 improved = True
 while improved:
      improved = False
      for i in range(1, len(route)-2):
           for j in range(i+1, len(route)):
                if j-i == 1: continue # changes nothing, skip then
                new_route = route[:]
                new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
                if cost(new_route) < cost(best):
                     best = new_route
                     improved = True
      route = best
 return best

这个算法的时间复杂度是多少？这是 2 opt 交换算法

标签： pythongreedy

Answer 1

从我的解释来看，它将是比较所有边缘 O(N^2) 的嵌套 for 循环，并且每次发现改进时，都这样做。上）。总共 O(N^3)。