这个贪婪搜索TSP的大时代复杂性是什么？

Question

我只是想要一些澄清/保证，看看这个GitHub here上的代码，OnO的时间复杂度的大O符号，因为它与问题中的顶点/城市数量成正比吗？

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是城市的数量。