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

Question

У меня есть общее взвешенное дерево (неориентированный граф без циклов, связанный) с n узлами и n-1 ребрами, соединяющими узел с другим.

Мой алгоритм выполняет следующие функции:

сделать

• вычислить фактический листьев (узлов с 1-й степени)

• удалить все листья и их края от маркировки дерева каждый родитель с максимальным значением стоимости его связанных листов (например, если внутренний узел соединен с двумя листами с краями с затратами 5,6, то мы лаборатория эш внутренний узел после удаления листьев с 6)

до дерева имеет размер < = 2

вернет узел с максимальной стоимостью маркированы

Могу ли я сказать, что сложность O(n), чтобы вычислить листья и O(n), чтобы устранить каждый край с листом, поэтому у меня есть O(n)+O(n) = O(n)?

Answer 1

Это, безусловно, можно сделать в O(n), но зависит от того, действительно ли ваш алгоритм действительно работает.

Если либо «вычислить фактические листья», либо «удалите все листья и их края» на всем дереве, этот шаг займет O(n).

И оба вышеуказанных шага будут повторяться O(n) раз в худшем случае (если дерево сильно неуравновешенное), значит, в целом он может принимать O(n2).

Для этого в O(n) вы можете указать, что каждый узел указывает на его родительский элемент, чтобы вы могли удалить лист в постоянное время и сохранить коллекцию листьев, чтобы у вас всегда были листья, вместо того чтобы их вычислять - это было бы приводят к O(n) времени работы.

Answer 2

Как ваше дерево является искусным. Он также может быть списком ссылок, и в этом случае вы должны удалить один узел на каждой итерации, и вам понадобится (n-2) итераций O(n), чтобы найти лист.

Так что ваш алгоритм на самом деле O(N^2)

Вот лучше алгоритм, который делает это в O(N) для любого дерева

deleteLeaf(Node k) { 

for each child do 
    value = deleteLeaf(child) 
    if(value>max) 
     max = value 
    delete(child) 
return max 
} 
deleteLeaf(root) or deleteLeaf(root.child) 

Answer 3

Вы можете легко сделать это в O (N) с набором реализованного как простой список, очередь или стек (порядок обработки неважен).

Положить все листья в комплект.

В цикле удалите лист из набора, удалите его и его край из графика. Обработайте метку, обновив макс родителя. Если родительский лист теперь является листом, добавьте его в набор и продолжайте движение.

Когда набор пуст, вы закончили, и метки узлов верны.

Первоначально построение множества - O (n). Каждая вершина помещается на множество, удаляется, а ее метка обрабатывается ровно один раз. Это все время. Таким образом, для n узлов это время O (n). Таким образом, мы имеем O (n) + O (n) = O (n).