Решение рекуррентных уравнений с дробями с использованием метода рекурсивного дерева

Я пытаюсь понять, как решать рекуррентные уравнения, и я могу легко решить их, используя метод рекурсивного дерева, если уравнение выглядит примерно так, например:

T(1) = 1;
T(n) = n + 2T(n/2) for n > 1

Но у меня возникли проблемы с пониманием того, как решать уравнения, для которых повторение изменяется на дробь, например, например:

T(1) = 1;
T(n) = n + 3/2T(.9n) for n > 1

Как в дереве может быть 3/2 ветки? Нельзя ли решить это с помощью деревьев рекурсии? Может ли кто-нибудь точно объяснить, как это будет работать в методе дерева рекурсии? Или есть другой метод, который был бы проще для этой формы уравнения?


recursion recurrence algorithm tree
person movac    schedule 01.03.2016    source источник
comment
теорема мастера может быть удобной   -  person pola sai ram    schedule 01.03.2016

Ответы (1)


arrow_upward
2
arrow_downward

Как может быть 3/2 th ветки?

Легко: у вас есть 4 ответвления на шаге x, затем на шаге x + 1 у вас будет 4 * 3 / 2 = 6 ответвления (если вы не можете разделить числа, используйте пол).

Может ли кто-нибудь точно объяснить, как это будет работать в методе дерева рекурсии?

Вы разворачиваете рекурсию, создаете огромную сумму, замечаете сходство и сходитесь.

Есть ли другой метод, который был бы проще для этой формы уравнения?

Да, люди сделали то, что я описал в предыдущем шаге для общей рекурсии T(n) = a T (n/b) + f(n) и создал теорему. Все, что вам нужно, это запомнить это (на самом деле вам нужно это понять), и вы можете решить любую эту рекурсию.

person Salvador Dali    schedule 01.03.2016