Рубрики

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

В следующей функции C пусть n> = m.

int gcd(n,m)

{

  if (n%m ==0) return m;  

  n = n%m;

  return gcd(m, n);

}

Сколько рекурсивных вызовов выполняется этой функцией?
(А) (LOGN)
(В) (П)
(С) (Loglogn)
(D) (SQRT (п))
(А) А
(Б) Б
(С) С
(D) D

Ответ: (А)
Объяснение: Выше код представляет собой реализацию евклидова алгоритма для нахождения наибольшего общего делителя (GCD).
Пожалуйста, смотрите http://mathworld.wolfram.com/EuclideanAlgorithm.html для сложности времени.
Тест на этот вопрос

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

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

0.00 (0%) 0 votes