这种贪婪搜索 TSP 的大 O 时间复杂度是多少？

Question

我只想要一些 clarification/reassurance，查看此 GitHub here 上的代码，时间复杂度的 Big O 表示法是否为 On2，因为它与问题中 vertices/cities 的数量？

Answer 1

该代码依赖于城市的距离矩阵：

def getDistanceMatrix(cities):
    distanceMatrix = []
    for currentNode in cities:
        subArray = []
        for comparisonNode in cities:
            subArray.append(getDistanceBetweenTwoCities(currentNode, comparisonNode))
        distanceMatrix.append(subArray)
    return distanceMatrix

因此顺序为 O(n^2)，其中 n 是城市的数量。