Временная сложность проблемы, связанной с деревом

Question

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

Предположим, у вас есть произвольное дерево. Алгоритм таков, что для каждого узла в дереве вы должны выполнить некоторую операцию O (1) столько раз, сколько у этого узла число потомков листа. Итак, в приведенном ниже примере дерева мы выполнили бы 2 операции для узла A и 6 операций для корневого узла R.

Допустим, у вас есть n узлов, дерево имеет глубину d, и вы можете использовать любые другие необходимые обозначения. В чем сложность?

Я не могу обернуть голову вокруг этого. Конечно, это меньше, чем O (n ^ 2), но как мне подойти к этому? Спасибо!

Редактировать: листовой потомок узла является потомком, у которого нет дочерних элементов. Потомок - это узел, достижимый путем повторного перехода от родителя к потомку (не имеет значения, является ли он внутренним или конечным узлом)

Answer 1

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

Answer 2

Это Ө (n ^ 2) .Очевидно, как вы заметили, он находится в O (n ^ 2) , потому что у каждого узла должно быть меньше, чем n дочерних листьев.

В дереве с конструкцией, подобнойэто:

     A
    /  \
   B    C
       / \
      D   E
         / \
        F   G
             ...

Самые верхние n / 4 внутренние узлы имеют по крайней мере n / 4 дочерних листьев, поэтому общее количество операций не менее n ^ 2/16 , который находится в Ω (n ^ 2) .

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