21.03

1. Асимптотический анализ рассмотренных задач. Алгоритмы сравнения строк.

Лекция 4
Курс «Динамическое программирование»

2. Сложность решения задачи о роботе методом полного перебора

1
4 10 20 35
1
3
6 10 15
1
2
3
4
5
1
1
1
1
1
• Для поля 4*5 робот должен сделать 3 шага вверх, 4
шага вправо.
• В любом случае робот делает 7 шагов.
• Далее нужно выбрать, где в последовательности из 7
шагов робот сделает 3 шага вверх (либо 4 шага вправо).
• Для этого есть формула сочетаний без повторений:
7!
3
4
n
Cn+m = C7 = C7 =
= 35
3!∙4!
• В общем случае, количество операций – T(n, m) =
n
Cn+m

3. Сложность решения задачи о роботе методом полного перебора

(2, 0)
(1, 0)
(1, 1)
(0, 0)
(0, 1) (0, 2)
Всего рекурсивных вызовов для
движения вверх – 2m−1 , для
движения вправо – 2n−1 .
Комбинируем вызовы – и
получаем 2m−1 ∙ 2n−1 = 2n+m−2 .
Поэтому сложность алгоритма –