Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 81

GATE

Рассмотрим следующую 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 )

Ответ: (Б)
Объяснение: Обратите внимание, что функция foo () является рекурсивной. Сложность пространства равна O (n), поскольку одновременно может быть не более O (n) активных функций (фреймов вызова функций).
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2005 | Вопрос 81

0.00 (0%) 0 votes