Основная теорема не применима?

Дано следующее рекурсивное уравнение

$$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ мы хотим применить основную теорему и отметить, что

$$n^{\log_2(2)} = n.$$

Теперь мы проверим первые два случая для $\varepsilon > 0$ , то есть

• $n\log n \in O(n^{1-\varepsilon})$ или
• $n\log n \in \Theta(n)$ .

Два случая не удовлетворены. Таким образом, мы должны проверить третий случай, то есть

• $n\log n \in \Omega(n^{1+\varepsilon})$ .

Я думаю, что третье условие также не выполняется. Но почему? И что было бы хорошим объяснением того, почему основная теорема не может быть применена в этом случае?

Три случая основной теоремы, на которые вы ссылаетесь, доказаны во введении к алгоритмам Томасом Х. Корменом, Чарльзом Э. Лейзерсоном, Рональдом Л. Ривестом и Клиффордом Стейном (2-е издание, 2001).

Правильно замечено, что рассматриваемая повторяемость находится между случаем 2 и случаем 3. То есть растет быстрее, чем n, но медленнее, чем n 1 + ε для любого ε > 0 .$f(n) = n \log n$$n$$n^{1+\varepsilon}$$\varepsilon > 0$

Однако теорема может быть обобщена, чтобы охватить это повторение. Рассматривать

Случай 2А. Рассмотрим для некоторого k ≥ 0 .$f(n) = \Theta (n^{\log_b a }\log_b^k n)$$k\geq 0$

Этот случай сводится к случаю 2 , когда . Интуитивно ясно , что вдоль каждой ветви дерева повторения F ( х ) добавляется thetas ; ( лог б п ) раз. Эскиз более формального доказательства можно найти ниже. Окончательный результат в том , что$k = 0$$f(x)$$\Theta (\log_b n)$

.

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$

В введении к алгоритмам это утверждение остается в качестве упражнения.

Применяя это утверждение к рассматриваемой рекурсии, мы, наконец, получаем

$$T(n) = \Theta(n \cdot \log^2 n).$$

Более подробную информацию об основной теореме можно найти на превосходной (imho) странице Википедии .

Поскольку @sdcvvc указывает в комментариях, чтобы доказать, что случай 3 здесь не применим, можно использовать правило Л'Оспиталя, которое гласит, что для любых функцийF(х)иг(х)дифференцируема в окрестностис. Применяя это кF(п)=пвойтипиг(п)=п1+εможно показатьчтожурналп∉thetas(п1+ε)

$$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$$ $f(x)$$g(x)$$c$$f(n) = n \log n$$g(n) = n^{1+\varepsilon}$$\log n \not\in \Theta (n^{1+\varepsilon}).$

---

Набросок доказательства основной теоремы для случая 2А.

Это воспроизведение частей доказательства из введения в алгоритмы с необходимыми модификациями .

Сначала докажем следующую лемму.

Лемма А:

Рассмотрим функцию , где ч ( п ) = п войти б в журнал K б н . Тогда g ( n ) = n log b a log k + 1 b n

$$g(n) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$$ $h(n) = n^{\log_b a} \log_b^k n.$$g(n) = n^{\log_b a} \log_b^{k +1} n.$

Доказательство: подставляя в выражение для g ( n ), можно получить g ( n ) = n log b a log k b$h(n)$$g(n)$

$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

QED

$n$$b$

$$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$$ $$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j T(n/b^j).$$ $f(n)$$\Theta(n^{\log_b a} \log_b^k n)$$\Theta$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

$n$$b$

Теорема Акра-Бацци является строгим обобщением основной теоремы. В качестве бонуса его доказательство - метель интегралов, которые заставят вашу голову вращаться ;-)

$T(n) \sim g(n)$