Zmiana zmiennych w relacjach powtarzalności

Obecnie uczę się samouczka Wprowadzenie do algorytmów (CLRS) i istnieje jedna szczególna metoda, którą opisują w książce w celu rozwiązania relacji nawrotów.

W tym przykładzie można zilustrować następującą metodę. Załóżmy, że mamy powtórzenie

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

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

Początkowo dokonują podstawienia m = lg (n), a następnie podłączają go ponownie do rekurencji i uzyskują:

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

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

Do tego momentu doskonale rozumiem. Ten następny krok jest dla mnie mylący.

Teraz „zmieniają nazwę” nawrotu i pozwalają , co najwyraźniej daje $S(m)$ $S(m) = T(2^m)$

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

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

Z jakiegoś powodu nie jest dla mnie jasne, dlaczego ta zmiana nazwy działa, a po prostu wygląda na oszustwo. Czy ktoś może to lepiej wyjaśnić?

— goooser
źródło

Odpowiedzi:

To na pewno nie oszustwo. Zastanów się, jak można zastosować podstawienie do rozwiązania trudnej całki. Podstawienie sprawia, że równanie jest łatwiejsze do manipulacji. Ponadto podstawienie może przekształcić nieco skomplikowane nawroty w znane.

Tak właśnie było w twoim przykładzie. Definiujemy nowy nawrót . Pamiętaj, że $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 (m) = 2 S (m / 2) + m .

$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)$

— Nicholas Mancuso
źródło

Tak, całkowicie rozumiem, w jaki sposób podstawienie ułatwia problemy i jak ponownie podłączyć wartości, aby uzyskać złożoność w kategoriach n. Wydaje mi się, że moje pytanie brzmi: po otrzymaniu S (m) = T (2 ^ m), jak wyprowadzić S (m / 2)? Z jakiegoś powodu jest to dla mnie nieoczywiste. Mówiąc ściślej, jak wyciągnąć wniosek, że T (2 ^ (m / 2)) = S (m / 2). Wydaje się, że w nawrotu T wielkość subproblem jest jako kwadrat korzenie, a w nawrotu S wielkość subproblem jest o połowę

Jedyną częścią, której nie rozumiem, jest powiedzenie „Zauważ, że S (m / 2) = T (2 ^ (m / 2))” To jedyna część, która jest dla mnie nieoczywista. Przyzwyczaiłem się do dokonywania podstawień zmiennych, ale tak naprawdę nie przywykłem do podstawiania całej rekurencji.

Ach, dobra, ta ostatnia edycja zrobiła to dla mnie. Teraz jest jasne, dzięki!

Mam małe wątpliwości. Jeśli piszę funkcji S () pod względem kjestem coraz niżej równania S (k) = 2S (k / 2) + m Jak mogę uzyskać substytut mdlak

— Atinesh

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

$S$

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

Dlatego przejścia to:

m \to 2^{m} \to T (2^{m}) = S (m)

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

\frac{m}{2} \to 2^{m / 2} \to T (2^{m / 2}) = S (\frac{m}{2}) .

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

— Vivek Anand Sampath
źródło