Я изо всех сил пытаюсь выяснить временную сложность следующей проблемы (это не домашняя работа, просто что-то, что я придумал и не могу понять).
Предположим, у вас есть произвольное дерево. Алгоритм таков, что для каждого узла в дереве вы должны выполнить некоторую операцию O (1) столько раз, сколько у этого узла число потомков листа. Итак, в приведенном ниже примере дерева мы выполнили бы 2 операции для узла A и 6 операций для корневого узла R.
Допустим, у вас есть n узлов, дерево имеет глубину d, и вы можете использовать любые другие необходимые обозначения. В чем сложность?
Я не могу обернуть голову вокруг этого. Конечно, это меньше, чем O (n ^ 2), но как мне подойти к этому? Спасибо!
Редактировать: листовой потомок узла является потомком, у которого нет дочерних элементов. Потомок - это узел, достижимый путем повторного перехода от родителя к потомку (не имеет значения, является ли он внутренним или конечным узлом)