2011-gre-cs-practice-book.pdf/Q01

Вопрос: Q01-08c765

Рассмотрим следующий псевдокод рекурсивной функции goAgain

// assume N is a positive integer
integer goAgain ( integer a, integer N )
begin
 if ( N == 1 ) then
  return a
 else
  return a + goAgain ( a, N/2 )
end

Каков порядок роста в зависимости от N количества рекурсивных вызовов функции goAgain?

Ответы

• Правильный ответ:

Объяснение

Исходники — вопрос 1 на 14 странице книги «2011-gre-cs-practice-book.pdf»

Не уверен что тут действительно нужно какое-либо объяснение, но все же.

•  — верно, поскольку функция каждый раз вызывает себя же с аргументом N вдвое меньшим, чем приняла на вход. В итоге к примеру для N = 16 функция будет вызвана со следующими аргументами: 16, 8, 4, 2, 1 — всего 5 раз, что соответствует ассимптотике .
•  — данная ассимптотика предполагает более чем линейный рост количества вызовов функции относительно N, что очевидно не так.
•  — данная ассимптотика предполагает рост количества вызовов функции линейно зависимый от N. Однако это очевидно не так.
•  — данная ассимптотика предполагает квадратичный рост количества вызовов функции в зависимости от N, что очевидно не верно.
•  — данная ассимптотика предполагает кубический рост количества вызовов функции в зависимости от N, что очевидно не так.

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

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

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