Сложность жадного алгоритма

Question

Я создал жадный алгоритм, который решает проблему минимально-взвешенных гамильтоновых цепей. Алгоритм всегда выбирает самый дешевый край, если нет способа найти схему из текущего набора ребер, тогда алгоритм отбрасывает последний край и выбирает следующий самый дешевый. Я не уверен насчет сложности этого алгоритма, может кто-нибудь объяснить мне это Вот псевдокод

    HC(currentVertex,expandedVertices,path,sum,N)
    if size(expandedVertices)==N then
        print(path)
        return sum
    end if
    expandedVertices.add(currentVertex)
    vertices=getAdjacentNodes(expandedVertices)
    sort(vertices)
    for i=1 to size(vertices) do
        path.append(vertices[i])
        cost=HC(vertices[i],expandedVertices,path,sum+getEdgeCost(currentVertex,
           vertices[i]),N)
        if(cost>0) then
            break
        end if
        path.remove(vertices[i])
    expandedVertices.remove(currentVertex)
    return cost

Answer 1

Ваш алгоритм использует грубую силу, чтобы найти путь, поэтому максимальное время выполнения O(n!) (для полностью связного графа). Может быть только один возможный маршрут, последний, который вы проверите.

В большинстве реальных случаев этот алгоритм будет быстрее. На проблему обычно ссылается другое название: проблема коммивояжера. В Википедии есть список хороших алгоритмов и эвристик, которые работают быстрее, чем у вас.