Рубрики

Алгоритмы | Анализ алгоритмов | Вопрос 19

Алгоритмы Задачи

Рассмотрим следующие две функции. Каковы временные сложности функций?

int fun1(int n)

{

    if (n <= 1) return n;

    return 2*fun1(n-1);

}

int fun2(int n)

{

    if (n <= 1) return n;

    return fun2(n-1) + fun2(n-1);

}

(A) O (2 ^ n) для fun1 () и fun2 ()
(B) O (n) для fun1 () и O (2 ^ n) для fun2 ()
(C) O (2 ^ n) для fun1 () и O (n) для fun2 ()
(D) O (n) для fun1 () и fun2 ()

Ответ: (Б)
Пояснение: Временная сложность fun1 () может быть записана как
T (n) = T (n-1) + C, который является O (n)

Временная сложность fun2 () может быть записана как
T (n) = 2T (n-1) + C, который является O (2 ^ n)

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

Алгоритмы | Анализ алгоритмов | Вопрос 19

0.00 (0%) 0 votes