Какова будет большая сложность времени этого жадного поиска TSP?

Question

Я просто хочу получить некоторые пояснения / заверения, глядя на код на этом GitHub здесь , будет ли запись Big O для сложности времени по On2, поскольку она прямо пропорциональна количеству вершин / городовв проблеме?

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 - количество городов.