#algorithm
#алгоритм
Вопрос:
некоторые рекурсивные вызовы имеют дублирующуюся работу. Например, в следующем случае выполняется
T(n) = (sum from i to zero to (n-1) T(i) ) n
T(0)=1 с. существует один (прямой) рекурсивный вызов каждого размера от 0 до n -1,
плюс O (n) дополнительная работа.
Решая для T (n), мы обнаруживаем, что оно растет экспоненциально.
Какое дерево генерирует рекурсивный вызов выше, это то же самое, что разделяй и властвуй дерево?
Спасибо!
Комментарии:
1. это рекуррентное отношение, оно не генерирует никаких вызовов…
2. Я не уверен в том, о чем вы спрашиваете. Приведенная выше функция представляет собой рекуррентное отношение, которое является типом математических функций. В математике нет такого понятия, как «рекурсивный вызов». Вы получаете рекурсивные вызовы, когда пытаетесь реализовать эту функцию наивным способом (могут быть лучшие способы). Также вы упоминаете дублирующую работу. Да, в наивной реализации есть дублирующая работа, которую можно легко устранить, не используя рекурсию для вычисления этой функции (например, динамическое программирование).
Ответ №1:
Я попытаюсь дать некоторый ответ на это… формулировка плохая, но, возможно, вы можете воспользоваться этим и использовать мое понимание, чтобы уточнить свой смысл.
Предположим, вы спрашиваете о функции для вычисления T (n), реализованной рекурсивно как
T(n)
1. r := 0
2. for i := 0 to n-1 do
3. r := r T(i)
4. r := r n
5. return r
Дерево для этой рекурсии будет выглядеть следующим образом…
_______________________T(n)_____________________
/ / /
T(0) T(1) T(2) T(3) ... T(n-1)
| / / | |
T(0) T(0) T(1) T(0) T(1) T(2) ... ...
... ... ....
Дерево очень похоже на дерево рекурсии, которое вы получаете для вычисления последовательности Фибоначчи; фактически, вы получаете то же самое дерево, если вы ограничиваете суммирование между [n-2, n-1] вместо [0, n-1] . Чтобы найти время выполнения этого, поскольку нерекурсивная часть функции равна O (1), нам просто нужно подсчитать, сколько сделано рекурсивных вызовов.
T(n) выполнит n рекурсивных вызовов, T(0), T(1), …, T(n-1). В результате вызова T(n), T(n-1) будет вызван только один раз; T(n-2) будет вызван дважды (один раз в результате T(n), снова в результате T(n-1)). T(n-3) будет вызван один раз в результате T(n), один раз в результате T(n-1) и дважды в результате двух вызовов T(n-2), всего 4 вызова. Как мы теперь видим, T (n-k) вызывается 2 ^ (k-1) раза в результате T (n); l итак, если мы суммируем количество вызовов для каждого k от 1 до n, мы получаем 2 ^ n — 1 … верно? Таким образом, мы получаем временную сложность для этой функции O (2 ^ n)… точно так же, как наивный Фибоначчи.
Чтобы получить скорость роста значения, возвращаемого функцией, мы можем рассматривать саму функцию как рекуррентное отношение некоторого другого фрагмента кода. В этом случае мы можем начать перечислять несколько терминов…
T(0) = c
T(1) = c 1
T(2) = c (c 1) 2 = 2c 1 2
T(3) = c (c 1) (2c 1 2) 3 = (4c 1 1 2 3)
T(4) = c (c 1) (2c 1 2) (4c 1 1 2 3) 4 = 8c 1 1 1 1 2 2 3 4
...
T(n) = c*2^(n-1) 1*2^(n-2) 2*2^(n-3) 3*2^(n-4) ... (n-1)*2^0 n
= c*2^(n-1) sum(i*2^(n-i-1) for i := 1 to n-1) n
Мы можем немного упростить это суммирование…
T(n) = c*2^(n-1) * 2^(n-1)*sum(i*2^(-i) for i := 1 to n-1) n
Таким образом, проблема получения решения замкнутой формы для порядка роста функции сводится к нахождению порядка роста суммирования i*2^(-i). Мои деньги говорят, что вы можете добиться большего, чем порядок роста… существует ли для этого закрытая форма? В любом случае, этого должно быть достаточно, чтобы помочь, если не дать полный ответ на ваш вопрос.