Изменение переменных в рекуррентных отношениях

В настоящее время я изучаю введение в алгоритмы (CLRS) и есть один конкретный метод, который они описывают в книге для решения рекуррентных отношений.

Следующий метод может быть проиллюстрирован на этом примере. Предположим, у нас есть рецидив

T (n) = 2 T (\sqrt{n}) + \log n

$T(n) = 2T(\sqrt n) + \log n$

Первоначально они делают замену m = lg (n), а затем подключают ее снова к повторению и получают:

T (2^{m}) = 2 T (2^{\frac{m}{2}}) + m

$T(2^m) = 2T(2^{\frac{m}{2}}) + m$

До этого момента я прекрасно понимаю. Этот следующий шаг меня смущает.

Теперь они «переименовывают» рекуррентность и позволяют , что, по-видимому, приводит к $S(m)$ $S(m) = T(2^m)$

S (м) знак равно 2 S (м / 2) + м

$S(m) = 2S(m/2) + m$

По какой-то причине мне не понятно, почему это переименование работает, и это просто кажется обманом. Кто-нибудь может объяснить это лучше?

asymptotics recurrence-relation mathematical-analysis landau-notation goooser
источник

Ответы:

Это конечно не обман. Подумайте в исчислении, как замена может быть использована для решения сложного интеграла. Подстановка делает уравнение более управляемым для манипуляций. Кроме того, замена может превратить несколько сложных повторений в знакомые.

Это именно то, что произошло в вашем примере. Определим новое повторение . Помните, что $S(m)=T(2^m)$ . Обратите внимание, что $T(2^m) = 2T(2^\frac{m}{2}) + m$ . Если этот конкретный момент все еще неясен, пустьи обратите внимание, что все, что мы делаем, это. Теперь мы можем выразить, расширив его до: Решая длямы видим, что он разрешается нашему знакомому другу $S(m/2) = T(2^\frac{m}{2})$ $k =m/2$ $S(k) = T(2^k)$ $S(m)$

S (м) знак равно 2 S (м / 2) + м,

$S(m) = 2S(m/2) + m.$

S

$S$

. Теперь, когда мы решили

мы хотим выразить это через

. Чтобы сделать это, просто вставьте обратно наше первоначальное значение для

и мы получим

O (m \log m)

$O(m \log m)$

S

$S$

T (n)

$T(n)$

m

$m$

T \in O (\log n \log \log n)

$T \in O(\log n \log \log n)$

Николас Манкузо
источник

Хорошо, я полностью понимаю, как подстановка помогает облегчить проблемы и как вставить значения обратно, чтобы получить сложность с точки зрения n. Я предполагаю, что мой вопрос, после того, как вы позволили S (m) = T (2 ^ m), как вы получаете S (m / 2)? Это просто не очевидно для меня по какой-то причине. Чтобы быть более конкретным, как вы пришли к выводу, что T (2 ^ (м / 2)) = S (м / 2). Кажется, что в повторении T размер подзадачи имеет квадратный корень, в то время как в повторении S размер подзадачи уменьшается вдвое

Единственная часть, которую я не понимаю, это когда вы говорите: «Заметьте, что S (m / 2) = T (2 ^ (m / 2))». Это единственная часть, которая не очевидна для меня. Я привык к идее подстановки переменных, но на самом деле я не привык к идее подмены целого повторения.

Ах, хорошо, это последнее редактирование сделало это для меня. Теперь понятно, спасибо!

Я немного сомневаюсь. Если я пишу функцию S () в терминах kя получаю ниже уравнения S (к) = 2S (к / 2) + м Как я могу получить замену mдляk

Atinesh

$S(m) = T(2^m)$ $S$ $T$ $m$ $2^m$

$S$

$S'$ $m$ $2^m$
$T$

Поэтому тогда переходы:

м \to 2^{м} \to T (2^{м}) знак равно S (м)

$m\to 2^m\to T(2^m) = S(m)$

\frac{м}{2} \to 2^{м / 2} \to T (2^{м / 2}) знак равно S (\frac{м}{2}),

$\tfrac{m}2\to2^{m/2}\to T(2^{m/2}) = S(\tfrac{m}2)\,.$

Вивек Ананд Сампат
источник