Содержание
- 2. Понятие Для некоторой задачи под подзадачей мы будем понимать: - ту же задачу, но меньшим числом
- 3. Рекуррентное уравнение соотношения, связывающие одни и те же функции, но с различными аргументами, называются рекуррентными уравнениями.
- 4. Правильное рекуррентное уравнение Рекуррентное уравнение называется правильным если значения аргументов у любой из функций правой части
- 5. Примеры T(n) = T(n - 1) + T(n - 2) T(n) = F(n - 2) +
- 6. Примеры рекуррентных уравнений 1. Нахождение максимального элемента из n элементов массива T(n) = T(n-1) + C=
- 7. Решение рекуррентных уравнений Метод итераций Подстановочный метод Метод рекурсивных деревьев
- 8. Метод итераций Метод заключается в том, что данное рекуррентное уравнение расписывается через множество других и затем
- 9. Пример 1 Найти методом итераций решение для рекуррентного уравнения: T(n) = 2T(n/2) + 5n2 T(1) =
- 10. Решение Для простоты мы предположим, что n является степенью 2 , т.е. n = 2к T(n)
- 11. Решение
- 12. Пример 2 Найти методом итераций решение для рекуррентного уравнения: T(n) = aT(n-1) + bn, 0 1,
- 13. Решение
- 14. Подстановочный метод Метод заключается в том, что методом подбора находится такая функция g(n), при подстановке которой
- 15. Пример Предположим, что необходимо решить следующее рекуррентное уравнение T(n) = 2T(n/2) + n g(n) ≥ 2g(n/2)
- 16. Пример Предположим, что необходимо решить следующее рекуррентное уравнение T(n) = 2T(n/2) + b g(n) ≥ 2g(n/2)
- 17. Метод рекурсивных деревьев На первой итерации формируется дерево следующего вида: - в корень дерева заносится свободный
- 18. Метод рекурсивных деревьев 3. Процесс построения древовидной структуры заканчивается, когда все значения висячих вершин равны Т(1)
- 19. Метод рекурсивных деревьев 4. После построения дерева суммирование значений в вершинах производится следующим образом: 1. Определяются
- 20. Пример Решить следующее рекуррентное уравнение T(n) = T(n/3)+T(2n/3)+n
- 21. Решение
- 22. Решение - сумма на каждом уровне равна n - количество уровней равно log3/2n T(n) = cnlog2n
- 23. Пример Решить следующее рекуррентное уравнение T(n) = T(n/5)+T(3n/4)+n
- 24. Решение
- 25. Решение T(n) = T(n/5)+T(3n/4)+n≤ ≤ n(1+q+q2+q3+…+qlog4/3n) ≤20n где q = 19/20. T(n) = O(n)
- 27. Скачать презентацию