Вычисление пространственной сложности C-функции?

Question

Рассмотрим следующую C-функцию:

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;
    }
}

Пространственная сложность вышеуказанной функции:

(a) O (1) (b) O (n) (c) O (n!) (d) O (n ^ n)

То, что я сделал, это вычисление отношения повторения для приведенного выше кода, но я все еще не могу решитьэто повторение.Я знаю, что это не сайт, связанный с домашней работой.Но любая помощь будет оценена.

Это мое возвращение.

T (n) = T (n-1) + T (n-2) + T (n-3) + T (n-4) + ........ + T (1) + S

Где S - некоторая постоянная.

Answer 1

Это будет зависеть от того, говорите ли вы о стеке или сложности кучи.

Для кучи это O(1) или O(0), так как вы не используете кучи памяти. (кроме базовой системы / программы)

Для стека это O(n). Это потому, что рекурсия поднимается на глубину N уровней.

Самая глубокая точка:

foo(n)
    foo(n - 1)
        foo(n - 2)

        ...

        foo(0)

Answer 2

Пространство сложности определяет, сколько места нужно вашей программе. Поскольку foo не объявляет массивы, для каждого уровня требуется O(1) пробел. Теперь все, что вам нужно сделать, это выяснить, сколько вложенных уровней может быть максимально активным одновременно.

Редактировать: ... так много, чтобы позволить вам найти решение для себя:)

Answer 3

Пространственная компактность будет O (n). Как вы упомянули, может показаться, что O (n * n), но следует помнить, что после того, как вызов say (i = 1) в цикле завершен, пространство, используемое для этого в стеке, удаляется. Итак, вам придется рассмотреть наихудший случай, когда i = n-1. Тогда максимальное количество рекурсивных вызовов функции будет в стеке одновременно

Answer 4

Вы не объясняете, как вы получили свое рекуррентное отношение. Я бы сделал это так:

1. Если n == 0, то foo использует постоянное пространство (рекурсия отсутствует).
2. Если n> 1, то foo повторяется один раз для каждого i от 0 до n-1 (включительно). Для каждой рекурсии он использует постоянное пространство (для самого вызова) плюс T (i) пространство для рекурсивного вызова. Но эти звонки происходят один за другим; пространство, используемое каждым вызовом, освобождается перед следующим вызовом. Поэтому их следует добавлять не просто, а просто по максимуму. Это было бы T (n-1), так как T не уменьшается.