Rygorystyczny dowód słuszności założenia

Twierdzenie Master jest pięknym narzędziem do rozwiązywania pewnych rodzajów nawrotów . Jednak często nakładamy połysk na integralną część podczas jej nakładania. Na przykład podczas analizy Mergesort z radością wychodzimy

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

biorąc pod uwagę tylko $n=2^k$ . Zapewniamy się, że ten krok jest prawidłowy - to znaczy $T \in \Theta(T')$ - ponieważ $T$ zachowuje się „ładnie”. Na ogół zakładamy, $n=b^k$ o $b$ wspólnego mianownika.

Łatwo jest tworzyć rekurencje, które nie pozwalają na to uproszczenie, używając błędnego $f$ . Na przykład powyżej nawrotu dla $T\,$ / $\,T'$ z

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

da $\Theta(n)$ przy użyciu twierdzenia Master w zwykły sposób, ale wyraźnie istnieje podsekwencja, która rośnie jak $\Theta(n \log n)$ . Zobacz tutaj inny, bardziej wymyślny przykład.

Jak możemy uczynić to „ładnym” rygorystycznym? Jestem całkiem pewien, że monotoniczność jest wystarczająca, ale nawet prosty nawrót Mergesorta nie jest monotoniczny; istnieje element okresowy (który dominuje asymptotycznie). Czy wystarczy zbadać $f$ i jakie są niezbędne i wystarczające warunki na $f$ które zapewniają, że twierdzenie Master działa?

asymptotics proof-techniques recurrence-relation master-theorem Raphael
źródło

Innym podejściem do tych samych wyników jest twierdzenie Akra-Bazzi „O rozwiązaniu równań liniowej rekurencji”, Optymalizacja obliczeniowa i zastosowania, 10 (2), 195-210 (1998) lub Drmota i Szpankowski „Twierdzenie o mistycznym podziale dyskretnym i Conquer Recurrences ”, SODA'11 < dl.acm.org/citation.cfm?id=2133036.2133064 >.

vonbrand

Oto link do powyższego artykułu, który nie znajduje się za zaporą.

Paresh,

IIRC zostało to omówione w rozdziale 4 CLRS

Kaveh

@Kaveh Dzięki za wskaźnik. W przeważającej części nazywają to „tolerowanym niechlujstwem”; w ich kontekście jest to w porządku, ponieważ zakładają oni, że wyprowadzacie tylko hipotezę, którą później udowodnicie przez indukcję. Wspominają o zagrożeniach (4.6). W 4.6.2 podają dowód, ale jest on na wysokim poziomie i nie mówią wprost, jakie ograniczenia na

muszą być wprowadzone. Wydaje się więc, że jest to coś w rodzaju „

takiego, że matematyka przechodzi”, co, jak sądzę, wymaga głównie, aby

miał „ładną” klasę

T

$T$

T

$T$

f

$f$

Θ

$\Theta$

Raphael

W ogólnym przypadku, gdy nie masz podobnych rozmiarów, możesz użyć metody Akra – Bazzi, która jest uogólnieniem twierdzenia głównego, upewnij się, jak zmienić konkretną funkcję na coś, co działa w tym twierdzeniu, wymaga trochę sztuczki, a dla czegoś takiego jak sortowanie według scalenia, tego zwykle używają ludzie, aby udowodnić złożoność czasu.

W tej odpowiedzi zakładamy, że i są nieujemne. Nasz dowód działa zawsze, gdy dla niektórych monotonicznych . Obejmuje to przykład Mergesort, w którym , i dowolną funkcję, która ma wielomianowe tempo wzrostu (lub nawet ). $f$ $T$ $f = \Theta(g)$ $g$ $f=\Theta(n)$ $\Theta(n^a \log^b n)$

Rozważmy najpierw przypadek, że jest monotoniczny i nie zmniejsza się (założymy to założenie później). Koncentrujemy się na nawrocie próbki Ten nawrót wymaga dwóch przypadków podstawowych, i . Przyjmujemy założenie, że $f$

T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) .

$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n).$

T (0)

$T(0)$

T (1)

$T(1)$

, które również relaksujemy później.

T (0) \leq T (1)

$T(0) \leq T(1)$

Twierdzę, że jest monotoniczny i nie maleje. Udowadniamy przez całkowitą indukcję, że . Jest to podane dla , więc niech . Mamy $T(n)$ $T(n+1) \geq T(n)$ $n = 0$ $n \geq 1$ Oznacza to, że Więc jeśli

\begin{aligned} T (n + 1) & = T (⌊ (n + 1) / 2 ⌋) + T (⌈ (n + 1) / 2 ⌉) + f (n + 1) \\ \geq T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) = T (n) . \end{aligned}

$\begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*}$

T (2^{⌊ \log_{2} n ⌋}) \leq T (n) \leq T (2^{⌈ \log_{2} n ⌋}) .

$T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}).$

, gotowe. Jest tak zawsze, gdy rozwiązanie dla potęg dwóch wynosi postać

T (2^{m}) = Θ (T (2^{m + 1}))

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

T (n) = Θ (n^{a} \log^{b} n)

$T(n) = \Theta(n^a \log^b n)$

$T(0) \leq T(1)$ $T'$ $T'(0) = T'(1) = \min(T(0),T(1))$ $T'(n) \leq T(n)$ $T''$ $T''(0) = T''(1) = \max(T(0),T(1))$ , a następnie . Przywołując twierdzenie Master, widzimy, że i dla tej samej funkcji , a więc . $T(n) \leq T''(n)$ $T'=\Theta(h)$ $T''=\Theta(h)$ $h$ $T = \Theta(h)$

Rozluźnijmy teraz założenie, że jest monotoniczny. Załóżmy, że dla niektórych funkcji monotonicznych . Zatem dla niektórych i wystarczająco dużych. Zakładamy, dla uproszczenia, że ; ogólny przypadek można rozpatrywać jak w poprzednim akapicie. Ponownie zdefiniować dwie nawrotów przez zastąpienie w (odpowiednio). Po raz kolejny twierdzenie Master da ten sam wynik (do stałych wielokrotności), który jest również identyczny (do stałych wielokrotności) z tym, co uzyskalibyśmy, rozwiązując pierwotną rekurencję tylko na potęgach dwóch. $f$ $f = \Theta(g)$ $g$ $cg(n) \leq f(n) \leq Cg(n)$ $c,C>0$ $n$ $n=0$ $T',T''$ $f$ $cg,Cg$

Yuval Filmus
źródło

W końcu muszę przeczytać to dokładniej. Fajnie dzięki! Pomyślałem, że zwrócę na to uwagę przyszłych czytelników (ponieważ się o to potknąłem): nie jest ograniczeniem, ponieważ jest tylko fałszem dla super wielomian i twierdzenie Master nie ma zastosowania do takich.

T (2^{m}) \in Θ (T (2^{m + 1}))

$T(2^m) \in \Theta(T(2^{m+1}))$

T

$T$

Raphael

Próbowałem zapisać swój dowód bardziej szczegółowo i utknąłem, dowodząc ostatniego zdania, „które jest również identyczne (...) z tym, co uzyskalibyśmy, rozwiązując pierwotną rekurencję tylko przy potęgach dwóch”. W szczególności musimy wykazać, że znajdujemy się w tym samym przypadku twierdzenia Master dla , i . Nie dotyczy to przypadków 1 i 2, ale nie mogę pokazać istnienia dla przypadku 3 (por. Wersja w CLRS, p94 w 3. wydaniu). Zastanawiałeś się nad tym, czy pracowałeś z wersją podobną do Wikipedii ?

c g

$cg$

f

$f$

C g

$Cg$

c < 1

$c < 1$

Raphael

To jest technika. Jeśli problem zniknie, patrz na przykład users.encs.concordia.ca/~chvatal/notes/master.pdf . Funkcja automatycznie spełni warunki. Wyobrażam sobie, że to samo działa dla i tak dalej. Alternatywnie, po prostu określ ten warunek bezpośrednio na zamiast na : musi istnieć jakiś „regularny” spełniający .

f = Θ (n^{α})

$f = \Theta(n^\alpha)$

g

$g$

f = Θ (n^{α} \log^{β} n)

$f = \Theta(n^\alpha \log^\beta n)$

g

$g$

f

$f$

g

$g$

f = Θ (g)

$f = \Theta(g)$

Yuval Filmus

Twierdziłeś, że „ monotonia” jest wystarczającym warunkiem (i uwierzyłem ci), więc próbowałem z tym pracować. Twierdzenie Master podane np. W CLRS dotyczy np. , jeśli się nie mylę, więc ograniczenie funkcji polilogarytmicznych lub coś takiego nie jest „techniczne”, ale odpowiednio osłabia wynik. Nawiasem mówiąc, podniesienie „regularności” do nie pomaga: mam już to w kluczowym przypadku dzięki regularności / (z założenia). Wracam więc do mojego poprzedniego komentarza, niestety. Jeśli to naprawdę tylko techniczne, nie widzę tego. Zbyt wiele nierówności.

g

$g$

f : n \mapsto 2^{n}

$f : n \mapsto 2^n$

g

$g$

c g

$cg$

C g

$Cg$

Raphael

Nadal uważam, że to techniczność. Martwisz się o stan techniczny. W przypadku większości funkcji pojawiających się w praktyce warunek zostanie zachowany. Pytasz o najbardziej ogólny warunek, pod jakim przechodzi powyższy szkic dowodu. To interesujące pytanie, na które jestem zbyt leniwy, aby na nie odpowiedzieć.

Yuval Filmus,

Rygorystyczny dowód słuszności założenia

Odpowiedzi: