Рубрики

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

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

    }

}

Предположим, что мы модифицируем вышеуказанную функцию foo () и сохраняем значения foo (i), 0 <= i <n, как и когда они вычисляются. С этой модификацией временная сложность для функции foo () значительно уменьшается. Пространственная сложность модифицированной функции будет:
(A) O (1)
(B) O (n)
(C) O (n!)
(D) O (n n )

Ответ: (Б)
Пояснение: Сложность пространства теперь также O (n).

Нам понадобится массив размером O (n). Пространство, необходимое для рекурсивных вызовов, будет равно O (1), поскольку значения будут взяты из сохраненного массива, а не вызовы функций снова и снова.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes