2001-gre-vs-practice.pdf/Q67

Вопрос: Q67-e5724f

Дан следующий фрагмент кода на C

int f(int x)
{
  if (x < 1)
  {
    return 1;
  } else
  {
    return f(x - 1) + g(x);
  }
}
 
int g(int x)
{
  if (x < 2)
  {
    return 1;
  } else
  {
    return f(x - 1) + g(x / 2);
  }
}

Какая функция лучше описывает скорость роста количества вызовов функции f(x)?

Ответы

• Логарифмическая
• Линейная
• Квадратичная
• Кубическая
• Правильный ответ: экспонента

Объяснение

Исходники — вопрос 67 на 45 странице книги «2001-gre-vs-practice.pdf»

Заметим, что каждый вызов функции f влечет за собой (за исключением случаев, когда аргумент < 1) вызов самой функции f и функции g, которая в свою очередь также вызывает функцию f и функцию g. Получается, что каждый вызов любой из этих функций создает еще по 2 вызова функции f. Получаем следующую цепочку количества вызовов функции f на каждом шаге: 1 -> 2 -> 4 -> 8 … Данная цепочка — ни что иное как экспонента , следовательно верный ответ — экспонента.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.