Блог

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

Код основан на матрице расстояний городов:

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