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

Question

Попытка выяснить, почему сложность О (п) для этого кода:

int sum(Node node) { 
    if (node == null) { 
     return 0; 
    } 
    return sum(node.left) + node.value + sum(node.right); 
} 

Узел:

class Node { 
    int value; 
    Node left; 
    Node right; 
} 

Это из CCI книги. Разве это не должно быть O (2^n), поскольку он выполняет итерацию через каждый узел?

Но это одно O (2^п), что для меня ясно, почему:

int f(int n) { 
if (n <= 1) { 
    return 1; 
} 
return f(n - 1) + f(n - 1); 
} 

Спасибо за помощь.

Answer 1

Алгоритм называется принять линейное время, или O (N) времени, если его временная сложность представляет собой О (п). Неформально это означает, что при достаточно большом входе размеры времени работы линейно увеличиваются с размером ввода. Например, для процедуры, которая объединяет все элементы списка, требуется время, пропорциональное длине списка.

From Wikipedia

Это очень разумно, что сложность alogrithm представляет собой О (п), так как рекурсивное число функциональных вызовов пропорциональна количеству элементов в дереве, есть п элементы в дереве и мы будем передавать каждый элемент только один раз, это звучит для меня очень линейно.

В отличие от другого алгоритма, который очень похож на рекурсивный алгоритм Fibonacci Sequence, этот алгоритм мы будем передавать каждое число от 1 до n намного больше, чем один раз, а не линейно пропорционально n, либо this объясняет, почему он имеет O (2^n).