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

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), но я застрял в том, как рассчитать временную сложность. Я также сделал дерево рекурсии, чтобы найти сложность пространства, но не смог вычислить, как рассчитать временную сложность. Может кто-нибудь помочь мне понять это и визуализировать.

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


c function recursion time-complexity space-complexity
person Sanjay Verma    schedule 12.04.2020    source источник
comment
красивая визуализация +1   -  person snr    schedule 12.04.2020

Ответы (1)


arrow_upward
3
arrow_downward

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

Как из структуры алгоритма, так и из изображения его рекурсивного дерева должно быть ясно, что T n для n> 0 состоит из все T i, 0 ‹= i‹ n, все соединены через один дополнительный узел. Немного подумав, вы должны увидеть, что можно построить T n +1 с помощью этой процедуры:

  • сделать копию T 'из T n
  • увеличить значение корня T 'на единицу
  • сделать корень T n потомком корня T ', чтобы сформировать T n +1

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

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

person John Bollinger    schedule 12.04.2020
comment
Хорошо, @John Bollinger, если мы используем одномерный массив для хранения результатов вызова функции, например, концепция динамического программирования, чтобы уменьшить вызов функции, тогда также сложность пространства будет O (n) для массива и O (1) для стека, но вот что будет временная сложность? - person Sanjay Verma; 12.04.2020
comment
Что ты думаешь по этому поводу, @SanjayVerma? Какую работу затем выполняет вызов foo(N)? - person John Bollinger; 12.04.2020