Решение рекуррентных уравнений, содержащих два рекурсивных вызова

15

Я пытаюсь найти $\Theta$ ; направляющийся следующего рекуррентного уравнения:

T (n) = 2 T (n / 2) + T (n / 3) + 2 n^{2} + 5 n + 42

$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$

Я считаю, что основная теорема неуместна из-за разного количества подзадач и разделов. Также рекурсивные деревья не работают, так как нет $T(1)$ или, вернее, $T(0)$ .

asymptotics recurrence-relation master-theorem Лаура
источник

5

Если у вас повторение этой формы, ДОЛЖЕН быть базовый случай, скажем,

T (n) \leq 42

$T(n) \leq 42$ для всех

n < 100

$n < 100$ . Если нет, то невозможно сказать, к чему приведет повторение: возможно,

T (n) = 2^{m}

$T(n) = 2^m$ для всех

n < 100

$n < 100$ , где

m

$m$ - размер исходной задачи! (вообразите рекурсию, которая заканчивается сравнением постоянного числа того, что вы повторяете со всеми подмножествами исходных элементов) Другими словами: ни один базовый случай не подразумевает недостаточно информации для решения рекурсии.

Алекс тен Бринк

15

Да, деревья рекурсии все еще работают! Неважно, происходит ли базовый случай при или или или даже . Также не имеет значения, каково реальное значение базового случая; Что бы это ни было, это константа. $T(0)$ $T(1)$ $T(2)$ $T(10^{100})$

При взгляде через очки большой тэты рецидив . $T(n) = 2T(n/2)+T(n/3)+n^2$

Корень дерева рекурсии имеет значение . $n^2$
Корень имеет трех дочерних элементов со значениями , и . Таким образом, общая стоимость всех детей . $(n/2)^2$ $(n/2)^2$ $(n/3)^2$ $(11/18) n^2$
Проверка работоспособности: корень имеет девять внуков: четыре со значением , четыре со значением и один со значением . Сумма этих значений . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Легко индукции доказательство предполагает , что для любого целого , то узлы на уровне имеют общее значение . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
Суммы уровня образуют нисходящий геометрический ряд, поэтому имеет значение только самый большой член . $\ell=0$
Мы заключаем, что . $T(n) = \Theta(n^2)$

JeffE
источник

14

Вы можете использовать более общий метод Акра-Бацци .

В вашем случае нам нужно найти такой, что $p$

\frac{1}{2^{п - 1}} + \frac{1}{3^{п}} знак равно 1

$\frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$

(что дает ) $p \approx 1.364$

и тогда у нас есть

T (Икс) знак равно Θ ({Икс}^{п} + {Икс}^{п} \int_{1}^{Икс} T^{1 - п} d T) знак равно Θ ({Икс}^{2})

$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$

Обратите внимание, что вам не нужно решать для . Все, что вам нужно знать, это то, что . $p$ $1 \lt p \lt 2$

Более простым методом было бы установить и попытаться доказать, что ограничена. $T(x) = x^2 g(x)$ $g(x)$

Арьябхата
источник

14

Пусть - сокращение для правой части повторения. Мы находим нижнюю и верхнюю границу для , используя : $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ $f$ $T(n/3) \leq T(n/2)$

3 T (n / 3) + 2 n^{2} + 5 n + 42 \leq f (n) \leq 3 T (n / 2) + 2 n^{2} + 5 n + 42

$3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$

Если мы используем нижнюю соотв. верхняя граница как правая часть рекуррентности, мы получаем в обоих случаях по основной теореме. Таким образом, ограничено сверху а снизу или, что то же самое, . $T'(n) \in \Theta(n^2)$ $T(n)$ $O(n^2)$ $\Omega(n^2)$ $T(n) \in \Theta(n^2)$

Для полного доказательства вы должны доказать, что является возрастающей функцией. $T$

Рафаэль
источник

давайте продолжим эту дискуссию в чате

Рафаэль

1

Этот трюк не будет работать для подобных рекурсий, таких как

, которые могут быть решены с помощью деревьев рекурсии. (Но даже деревья рекурсии не будут работать для

, что можно решить с помощью Akra-Bazzi.)

T (n) = 2 T (n / 2) + 3 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 3T(n/3) + n^2$

T (n) = 2 T (n / 2) + 4 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 4T(n/3) + n^2$

Джефф

Решение рекуррентных уравнений, содержащих два рекурсивных вызова

Ответы: