Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Анализ рекурсивных алгоритмов




При изучении темы "Рекурсия" полезно проанализировать рекурсивные алгоритмы с точки зрения последовательности их выполнения. Под последовательностью выполненного рекурсивного алгоритма будем понимать последовательность вызовов алгоритма с различными значениями аргументов и очередью определения результатов.

Рассмотрим сначала функцию расчетов факториала числа (см. выше)

Для алгоритма определения 5-го члена ряда Фибоначчи схема нахождения изображена на рисунке:

Чтобы определить значение 5-го элемента Фибоначчи, для этого необходимо определить значения fib(2), fib (1), fib (3), fib (2). Из схемы видно также, что в рассматриваемом случае значения fib (1), fib (3), fib (2) определяются дважды. При нахождении члена последовательности с большим номером число повторных вычислений значительно увеличивается. В результате при определения значения fib (17) компьютер выполнит свыше 1000, значения fib (31) свыше 1000000, значения fib (45) свыше 1000000000 операций сложения. В тоже время при использовании не рекурсивного алгоритма для вычисления 45-го члена потребуется всего 43 операции сложения.

Это позволяет сделать вывод о неэффективности использования рекурсии для решения рассматриваемой задачи. Аналогичный вывод можно сделать для решения других задач.






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных