Временная сложность и пространственная сложность следующего фрагмента кода

Question

double foo(int n)
{
    int i;
    double sum;
    if(n == 0)
    {
        return 1.0;
    }
    else
    {
        sum = 0.0;
        for(i = 0; i < n; i++)
        {
            sum += foo(i);
        }
        return sum;
    }

}

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

вот дерево рекурсии.

Answer 1

График, который вы представили, очень полезен для визуализации масштабирования времени алгоритма. Рассмотрим вопрос: какова связь между деревьями рекурсии T _n и T _{n + 1} для входных данных n и n + 1? Или, эквивалентно, с учетом T _n как можно построить T _{n + 1} ?

Это должно быть ясно как из структуры алгоритма, так и из описания его дерева рекурсии, что T _n для n > 0 состоит из всех T _i , 0 <= <em>i <<em> n , все соединены через один дополнительный узел. Немного подумав, вы сможете увидеть, что можно построить T _{n + 1} с помощью этой процедуры:

• сделать копию, T ', из T _n
• увеличивает значение root T' на один
• , получая root из T _n дочерний элемент root из T 'для образования T _{n + 1}

. конструкция, T _{n + 1} имеет в два раза больше узлов, чем T _n , поэтому сложность времени масштабируется как O (2 ⁿ ).

Вы уже ответили на свой вопрос о сложности пространства, но я утверждаю, что он соответствует высоте дерева и поэтому масштабируется как O ( п ).