Как бы я нашел временную сложность следующего рекурсивного алгоритма?

Question

Предполагая, что r является корнем дерева (может быть недвоичным), c является дочерним элементом r, и каждый узел содержит целое число.

Algorithm findMax(r)
if r = null return null
int maxValue = r.value
if r.isLeaf return maxValue;
for each child c of r do{
    if findMax(c) > maxValue
        maxValue = findMax(c)
}
return maxValue

Answer 1

В настоящее время он имеет сложность O (n), если считать n номером узла в дереве .

Для каждого дочернего узла корня вы вызываете рекурсивную функцию для всего корня поддерева в c.Таким образом, в основном, вы преформируете DFS на этом графе, который в O (V + E) -> в вашем случае, когда граф является деревом, равен O (V).

Обратите внимание, что вы называетерекурсивная функция findMax в операторе if - если она верна, вы вычисляете ее снова - что увеличивает сложность до O (2 * n).Вычислите функцию findMax один раз, присвойте ее результат локальной переменной, проверьте и обновите maxValue, чтобы уменьшить сложность до O (n).