Эксперименты для определения вычислительной сложности

В главе 4 было доказано, что решать задачу по поиску n-го числа Фибоначчи эффективнее методом динамического программирования. Проведем несколько экспериментов.

Рис 6.1. Работа программы

Результаты представлены в таблице и на графике.

Таб. 6.1. Таблица результатов вычисления числа Фибоначчи.

Рис. 6.2. График результатов вычисления числа Фибоначчи.

По результатам, представленным выше хорошо видно, что время вычисления с помощью динамического программирования значительно ниже в сравнении со временем вычисления рекурсией. Особенно хорошо видна разница при вычислении 40-го числа Фибоначчи и старше.

Также проведем несколько экспериментов по нахождению наибольшей общей последовательности. Результаты представлены в таблице и на рисунке ниже.

Выводы

Динамическое программирование действительно оказалось очень мощным методом. Его применение существенно облегчает решение многих сложных задач, которые нельзя решить другими методами. Укажем два признака, характерных для задач, решаемых методами динамического программирования.

• · Задача обладает свойством оптимальности для подзадач, т. е. оптимальное решение задачи содержит оптимальные решения ее подзадач.
• · Задача имеет перекрывающиеся подзадачи, т. е. при рекурсивном решении мы многократно выходим на одни и те же подзадачи.

При этом, наши исследования показали, что решение перекрывающихся подзадач значительно эффективнее именно динамическим программирование, а не вычислением рекурсии, хоть для написания первой программы понадобилось больше строк кода.