W informatyce często musimy rozwiązywać relacje powtarzalności , to znaczy znaleźć zamkniętą formę dla rekurencyjnie zdefiniowanej sekwencji liczb. Rozważając środowiska wykonawcze, często jesteśmy zainteresowani głównie asymptotycznym wzrostem sekwencji .

Przykładami są

1. Czas działania funkcji rekurencyjnej ogona schodzącej w dół do $0$ od $n$ którego ciało wymaga czasu $f(n)$ :

   $\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

2. Sekwencja Fibonacciego :

   $\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

3. Liczba słów Dyck z $n$ parami nawiasów:

   $\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

4. Ponowne uruchomienie środowiska wykonawczego scalesort na listach o długości :$n$

   $\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

Jakie są metody rozwiązywania relacji powtarzalności? Szukamy

• ogólne metody i
• metody znaczącej podklasy

jak również

• metody, które dają precyzyjne rozwiązania i
• metody zapewniające (związany) asymptotyczny wzrost.

^{To ma stać się pytaniem referencyjnym. Proszę zamieścić jedną odpowiedź dla każdej metody i podać ogólny opis oraz przykładowy przykład.}

Konwertowanie pełnej historii na historię ograniczoną

Jest to pierwszy krok w rozwiązywaniu nawrotów, w których wartość na dowolnej liczbie całkowitej zależy od wartości na wszystkich mniejszych liczbach całkowitych. Rozważmy na przykład powtarzalność która powstaje w analizie losowego szybkiego sortowania . (Tutaj, jest rangą losowo wybranego elementu przestawnego.) Dla dowolnej liczby całkowitej wartość zależy od wszystkich z . Nawroty tej formy nazywane są nawrotami pełnej historii .knT(n)T(k)k<

$$T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)$$ $k$$n$$T(n)$$T(k)$$k<n$

Aby rozwiązać ten nawrót, możemy go przekształcić w ograniczoną powtarzalność historii , w której zależy tylko od stałej liczby poprzednich wartości. Ale po pierwsze, pomaga to nieco uprościć nawrót, zebrać wspólne warunki i wyeliminować nieznośne frakcje. Teraz, aby przekonwertować na powtarzającą się historię , zapisujemy rekurencję dla , odejmujemy i ponownie gromadzimy warunki: n T ( n $T(n)$ T(n-1) ( n - 1 ) T ( n - 1

$$\begin{align*} n T(n) &= n^2 + 2\sum_{k=1}^{n-1} T(k) \end{align*}$$ $T(n-1)$ $$\begin{align*} (n-1) T(n-1) &= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k) \\ \implies nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1) \\[1ex] \implies n T(n) &= (2n-1) + (n+1) T(n-1) \\[1ex] \implies \frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n} \end{align*}$$

Teraz, jeśli zdefiniujemy i zastąpimy ułamek prostszą asymptotyczną formą , otrzymujemy znacznie prostszą rekurencję Rozszerzenie tej rekurencji do sumy natychmiast daje nam , gdzie jest tą liczbą harmonicznych . Stwierdzamy, że .2 n - $t(n) = T(n)/(n+1)$ Θ(1/n)t(n)=Θ(1/n)+t(n-1). t(n)=Θ(Hn)=Θ(logn)Hn$\frac{2n-1}{n(n+1)}$$\Theta(1/n)$

$$t(n) = \Theta(1/n) + t(n-1).$$ $t(n) = \Theta(H_n) = \Theta(\log n)$$H_n$$n$$\boldsymbol{T(n) = \Theta(n\log n)}$

Generowanie funkcji$\newcommand{\nats}{\mathbb{N}}$

Każda seria liczb odpowiada funkcji generującej . Często można go wygodnie uzyskać z powtórzenia, aby jego współczynniki - elementy serii - zostały zerwane.

Ta odpowiedź zawiera ogólny ansatz z kompletnym przykładem, skrót do specjalnego przypadku oraz kilka uwag na temat korzystania z tej metody w celu uzyskania asymptotyków (nawet jeśli nie można uzyskać dokładnego wyniku).

Metoda

Niech ciąg liczb. Następnie formalna seria mocy$(a_n)_{n\in\nats}$

$\qquad \displaystyle A(z) = \sum_{n=0}^\infty a_nz^n$

to zwykła funkcja generująca ¹ . Współczynniki rozszerzenia szeregu równe sekwencji, tj. . Na przykład zwykłą funkcją generowania znanych liczb katalońskich jest$(a_n)_{n\in\nats}$$A(z)$$[z^n]A(z) = a_n$ $C_n$

$\qquad \displaystyle C(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$ .

Definicja jest również naszą odpowiedzią na rozwiązanie problemu nawrotu. Działa to najlepiej w przypadku nawrotów liniowych, dlatego dla uproszczenia załóżmy, że forma jest powtarzalna$A$

$\qquad \begin{align} a_0 &= c_0 \\ &\vdots \\ a_{k-1} &= c_{k-1} \\ a_n &= f(n) + \sum_{i=1}^k b_i a_{n-i} \qquad , n \geq k \end{align}$

dla niektórych stałych i funkcja niezależna od wszystkich . Teraz po prostu wstawiamy zarówno kotwice, jak i część rekurencyjną do ansatz$b_1, \dots, b_k \in \mathbb{R}$$f(n) : \nats \to \nats$$a_i$

$\qquad \begin{align} A(z) &= \sum_{n=0}^\infty a_nz^n \\ &= c_0z^0 + c_1z^1 + \dots + c_{k-1}z^{k-1} + \sum_{n=k}^\infty \left[ f(n) + \left(\sum_{i=1}^k b_i a_{n-i}\right)\right] z^n \end{align}$

Stosując mechanikę manipulacji sumą, właściwości formalnych szeregów mocy i znane tożsamości ², ostatnia prawa strona musi zostać doprowadzona do postaci zamkniętej, zazwyczaj w kategoriach . Wynikowe równanie można (często) rozwiązać dla . Rozszerzenie szeregu wyniku (które można łatwo uzyskać, poznać lub w inny sposób uzyskać) jest zasadniczo rozwiązaniem.$A(z)$$A(z)$

Dobre wprowadzenie można znaleźć w książce Wilfa [3] oraz w GKP [4]. Zaawansowane materiały zostały zebrane przez Flajolet i Sedgewick [5].

Przykład

Rozważać

$\qquad \begin{align} a_0 &= 1 \\ a_1 &= 2 \\ a_n &= 5n + 3a_{n-1} - 2a_{n_2} \qquad , n > 1 \end{align}$

Obliczamy:

$\qquad \begin{align} A(z) &= \sum_{n=0}^\infty a_n z^n \\ &= 1 + 2z + \sum_{n=2}^\infty \left[ 3a_{n-1} - 2a_{n-2} + 5n\right]z^n \\ &= 1 + 2z + 3\sum_{n=2}^\infty a_{n-1}z^n - 2\sum_{n=2}^\infty a_{n-2}z^n + 5\sum_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z\sum_{n=1}^\infty a_nz^n - 2z^2\sum_{n=0}^\infty a_n z^n + 5\sum_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z(A(z) - a_0) - 2z^2A(z) + 5 \left( \frac{z}{(1-z)^2} - z\right) \\ &= 1 - 6z + (3z - 2z^2)A(z) + \frac{5z}{(1-z)^2} \end{align}$

To rozwiązuje

$\qquad \begin{align} A(z) &= \frac{1 - 3z + 13z^2 - 6z^3}{(1-2z)(1-z)^3} \\ &= \frac{16}{1-2z} - \frac{5}{1-z} - \frac{5}{(1-z)^2} - \frac{5}{(1-z)^3} \\ &= 16\sum_{n=0}^\infty 2^n z^n - 5\sum_{n=0}^\infty z^n - 5 \sum_{n=0}^\infty (n+1) z^n - 5\sum_{n=0}^\infty \frac{(n+1)(n+2)}{2} z^n \end{align}$

Teraz możemy wreszcie odczytać

$\qquad \begin{align} a_n &= 16 \cdot 2^n - 5 - 5(n+1) - \frac{5}{2}(n+1)(n+2) \\ &= 2^{n+4} - \frac{5}{2}n^2 - \frac{25}{2}n - 15 \end{align}$

Kiedy już się przyzwyczaisz , zauważysz, że to wszystko jest dość mechaniczne. W rzeczywistości algebra komputerowa może w wielu przypadkach zrobić to wszystko za Ciebie. Zaletą jest to, że pozostaje (mniej więcej) ta mechanika, nawet jeśli nawrót jest bardziej złożony. Zobacz tutaj bardziej angażujący, mniej mechaniczny przykład.

Zauważ też, że ogólne techniki działają również, jeśli poszukiwane obiekty są liczbami zespolonymi, a nawet wielomianami.

Skrót

Do liniowych i jednorodnych nawrotów, tj. Takich postaci

$\qquad \begin{align} a_0 &= c_0 \\ &\vdots \\ a_{k-1} &= c_{k-1} \\ a_n &= \sum_{i=1}^k b_i a_{n-i} \qquad , n \geq k \end{align}$

powyższe dzieje się za każdym razem dokładnie w ten sam sposób. Wykonując powyższe obliczenia symbolicznie, znajdujemy następujący lemat . Pozwolić

$\qquad \displaystyle z^k - b_1 z^{k-1} - b_2 z^{k-2} - \dots - b_k$

być charakterystycznym wielomianem (nawrotu). Niech ponadto (odrębne parami) zera wspomnianego wielomianu o wielokrotności odpowiednio . Następnie żądany współczynnik podaje$\lambda_1, \dots, \lambda_l$$r_i$

$\qquad \displaystyle a_n = \sum_{i=1}^l \sum_{j=1}^{r_i} b_{i,j} \cdot n^{j-1} \cdot \lambda_i^n$

z nieznanym . Ponieważ charakterystyczny wielomian ma stopień , istnieją dokładnie (zera) zera, tj. Suma do . W związku z tym, że brakujące Współczynniki mogą być określone poprzez rozwiązanie układu równań liniowych z równania uzyskane przez przyrównywanie powyższym wzorze z dowolnego o (np odnośniki).$b_{i,j}$$k$$k$$r_i$$k$$k$$k$$a_n$

Asymptotyki

Dotarcie do formularza zamkniętego dla jest zwykle najłatwiejszą częścią. Wyrażając to w generowaniu funkcji, wiemy, że współczynniki (jak w przykładzie) szybko stają się trudne. Przykładami są z góry i jedno dla liczby słów Dyck wymienionych w pytaniu.$A(z)$$C(z)$

Można zastosować złożoną maszynę analityczną, w szczególności analizę osobliwości, w celu uzyskania asymptotyków dla współczynników; modne słowa obejmują metodę Darboux i metodę siodła. Są one oparte na twierdzeniu pozostałości i integralnej wzorze Cauchy'ego . Szczegóły w [6].

---

1. Możesz robić podobne rzeczy za pomocą wykładniczej , Dirichleta i niektórych innych funkcji generujących. To, co działa najlepiej, zależy od sekwencji, a zwłaszcza od tego, czy znajdziesz niezbędne formularze zamknięte.
2. Na przykład z ściągawki TCS lub [3].
3. generowanie funkcji H. Wilfa (1994, wydanie 2) - dostępne do pobrania za darmo
4. Concrete Mathematics autorstwa RL Grahama, DE Knutha i O. Patashnika (1994, wydanie 2)
5. Wprowadzenie do analizy algorytmów R. Sedgewicka i P. Flajoleta (2. wydanie, 2013) - dostępne do pobrania za darmo
6. Analytic Combinatorics autorstwa P. Flajolet i R. Sedgewick (2009) - dostępne do pobrania za darmo

Twierdzenie mistrzowskie

Twierdzenie Główna daje asymptotyka roztworach tzw podzielić i podbijać powtórzeń, czyli takie, które dzielą ich parametrów do współmiernych kawałki (zamiast odcinania stałych). Zwykle występują one podczas analizy (rekurencyjnej) algorytmów dzielenia i zdobywania, stąd nazwa. Twierdzenie to jest popularne, ponieważ często jest niezwykle łatwe do zastosowania. Z drugiej strony można go stosować tylko w przypadku nawrotów następującej formy:

$\qquad \displaystyle T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$

z . Istnieją trzy przypadki$a \geq 1, b > 1$

1. $\quad \displaystyle f \in O\left( n^{\log_b (a) - \varepsilon} \right)$

   dla niektórych ;$\varepsilon > 0$

2. $\quad \displaystyle f \in \Theta\left( n^{\log_b a} \log^{k} n \right)$ ,

   dla niektórych ;$k \geq 0$

3. $\quad \displaystyle f \in \Omega\left( n^{\log_b (a) + \varepsilon} \right)$

   dla niektórych i$\varepsilon > 0$

   $\quad \displaystyle a f\left( \frac{n}{b} \right) \le c f(n)$

   dla niektórych i .$c < 1$$n \to \infty$

co implikuje asymptotyki

1. $T \in \Theta\left( n^{\log_b a} \right)$ ,
2. $T \in \Theta\left( n^{\log_b a} \log^{k+1} n \right)$ i
3. $T \in \Theta \left(f \right)$ ,

odpowiednio, kolejno. Zauważ, że przypadki podstawowe nie są tu podane ani użyte; to ma sens, zważywszy badamy jedynie asymptotyczne zachowanie. W milczeniu zakładamy, że są one stałymi (jakie jeszcze mogą być. Które stałe nie widzimy są nieistotne, wszystkie znikają w .$\Theta$

Przykłady

1. Rozważ powtórzenie

   $\qquad \displaystyle T(n) = 4T\left(\frac{n}{3}\right) + n$ .

   Przy i - zwróć uwagę, że widzimy, że przypadek 1 dotyczy . Dlatego .$f(n) = n, a=4$$b=3$$\log_b a \approx 1.26$$\varepsilon = 0.25$$T \in \Theta(n^{\log_3 4}) = \Theta(n^{1.261\dots})$

2. Rozważ powtórzenie

   $\qquad \displaystyle T(n) = 2T(n/2) + n$ .

   Przy i - zwróć uwagę, że widzimy, że drugi przypadek dotyczy . Dlatego .$f(n) = n, a=2$$b=2$$\log_b a = 1$$k=0$$T \in \Theta(n \log n)$

3. Rozważ powtórzenie

   $\qquad \displaystyle T(n) = 3T\left(\frac{n}{4}\right) + n$ .

   Z , a - Uwaga widzimy, że stosuje się w przypadku trzy i . Dlatego .$f(n) = n, a=3$$b=4$$\log_b a \approx 0.79$$\varepsilon = 0.2$$c=1$$T \in \Theta(n)$

4. Rozważ powtórzenie

   $\qquad \displaystyle T(n) = 16T\left(\frac{n}{4}\right) + n!$

   Mamy tu , , a- wiele standardowych przykładów będzie miało wielomian , ale nie jest to regułą. Mamy i przypadek trzeci obowiązuje ponownie. Choć w tym przypadku możemy wybrać dowolny oraz jak dla wszystkich . Stąd .$a = 16$$b=4$$f(n) = n!$$f$$\log_b a = 2$$\varepsilon$$c > 0$$n! \in \Omega(n^{k})$$k$$T \in \Theta(n!)$

Dalsza lektura

• Jest całkiem możliwe, że żaden przypadek twierdzenia Master nie ma zastosowania. Na przykład podproblemy mogą nie mieć równej wielkości lub mieć bardziej złożoną formę. Istnieją pewne rozszerzenia twierdzenia Master, na przykład Akra-Bazzi [1] lub Roura [2]. Istnieje nawet wersja, która działa w przypadku dyskretnych nawrotów (tj. Podłogi i sufity są używane w parametrach rekurencyjnych) i zapewnia ostrzejsze wyniki [3].

• Zwykle musisz masować rzeczywistą relację nawrotu, którą masz w kształcie, zanim będziesz mógł zastosować twierdzenie Master. Typowe transformacje, które zachowują asymptotyki, obejmują upuszczanie podłóg i sufitów, a także zakładanie . Uważaj, aby tu nie zniszczyć; szczegółowe informacje znajdują się w [4] sekcji 4.6 i tym pytaniu.$n=b^k$

---

1. O rozwiązaniu równań liniowej rekurencji M. Akry i L. Bazzi (1998)
2. Ulepszone główne twierdzenie o powtarzających się i dzielących powtórzeniach S. Roura (1997)
   ^{Odnosi się do innych ulepszonych twierdzeń głównych.}
3. Mistrzowskie twierdzenie o dyskretnych podziałach i zwycięstwach M. Drmoty i W. Szpankowskiego (2011)
4. Wprowadzenie do algorytmów Cormena i in. (2009, wydanie trzecie)

Zgadnij i udowodnij

Lub, jak lubię to nazywać, technika „ ”. Może być stosowany do wszystkich rodzajów tożsamości. Pomysł jest prosty:$\dots$

Odgadnij rozwiązanie i udowodnij jego poprawność.

Jest to popularna metoda, prawdopodobnie dlatego, że zazwyczaj wymaga trochę kreatywności i / lub doświadczenia (dobra do popisywania się), ale mało mechaniki (wygląda elegancko). Sztuka polega na robieniu dobrych, wykształconych domysłów; dowodem jest (w naszym przypadku) zwykle mniej lub bardziej prosta indukcja.

W przypadku nawrotów „zgadywania” zwykle dokonuje się za pomocą

• kilkakrotnie rozszerzając nawrót,
• zastanawianie się nad kotwicą i
• zgadywanie wzoru dla półproduktu ( ).$\dots$

Prosty przykład

$\qquad \begin{align} s_0 &= s_1 = s_2 = 1 \\ s_n &= 5s_{n-3} + 6 \qquad\qquad n \geq 2 \end{align}$

kilka razy definicję :$s_n$

$\qquad \begin{align} s_n &= 5s_{n-3} + 6 \\ &= 5(5s_{n-6} + 6) + 6 \\ &= 5(5(5s_{n-9} + 6) + 6) + 6 \\ &\ \vdots \\ &= \underbrace{5(5(5( \dots 5\cdot 1}_{n \div 3 \text{ times}} + \underbrace{6 \dots ) + 6) + 6) + 6}_{n \div 3 \text{ times}} \end{align}$

Tutaj wzór jest łatwy do wykrycia i prowadzi nas do roszczenia:

$\qquad \begin{align} s_n &= 5^{\left\lfloor\frac{n}{3}\right\rfloor} + 6\cdot \sum_{i=0}^{\left\lfloor\frac{n}{3}\right\rfloor - 1} 5^i \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \end{align}$

Teraz dowodzimy tożsamości przez indukcję. Dla możemy ustalić poprawność poprzez podłączenie odpowiedniej wartości. Zakładając, że tożsamość obowiązuje dla wszystkich dla dowolnego, ale ustalonego , obliczamy$n \in \{0,1,2\}$$n' \leq n$$n \geq 3$

$\qquad \displaystyle \begin{align} s_{n+3} &= 5s_n + 6 \\ &= 5\cdot \left( \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \right) + 6 \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor + 1} - \frac{6}{4} \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n+3}{3}\right\rfloor} - \frac{6}{4} \end{align}$

co potwierdza tożsamość dzięki sile indukcji.

Jeśli spróbujesz użyć tego przy bardziej zaangażowanych nawrotach, szybko napotkasz główną wadę tej metody: może być trudno zobaczyć wzór lub skondensować go do ładnej zamkniętej formy.

Asymptotyki

Możliwe jest stosowanie tej metody również w przypadku asymptotyków. Pamiętaj jednak, że musisz odgadnąć stałe symboli Landaua, ponieważ musi istnieć jedna stała, która ustanawia granicę dla wszystkich , tzn. Współczynnik stały nie może się zmienić podczas indukcji.$n$

Rozważmy na przykład powtarzalność środowiska wykonawczego Mergesort, uproszczoną w przypadku ¹:$n=2^k$

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= 2T(n/2) + n-1 \qquad n \geq 1 \end{align}$

My Chyba , że ze stałą , to jest . Udowadniamy to poprzez indukcję nad ; krok indukcyjny wygląda następująco:$T(n) \in O(n\log n)$$c=1$$T(n) \leq n\log n$$k$

$\qquad \begin{align} T(n) &= 2T(n/2) + n-1 \\ &\leq 2\frac{n}{2}\log \frac{n}{2} + n - 1 \\ &= n\log n - n\log 2 + n - 1 \\ &\lt n \log n \end{align}$

---

1. W przypadku nie malejących sekwencji naturałów każda nieskończona podsekwencja ma taki sam asymptotyczny wzrost jak sekwencja oryginalna.

Metoda Akra-Bazzi

Metoda Akra-Bazzi daje asymptotykę dla nawrotów postaci: Dotyczy to zwykłych powtórzeń dziel i zwyciężaj, ale także przypadków, w których podział jest nierówny. „ ” mogą na przykład uwzględniać podziały, które nie są dokładne. Warunki zastosowania to:

$$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for $x \ge x_0$}$$ $h_i(x)$

• Istnieje wystarczająca liczba przypadków podstawowych, aby rozpocząć nawrót
• i są stałymi$a_i$$b_i$
• Dla wszystkich ,$i$$a_i > 0$
• Dla wszystkich ,$i$$0 < b_i < 1$
• $\lvert g(x) \rvert = O(x^c)$ dla pewnej stałej jako$c$$x \rightarrow \infty$
• Dla wszystkich ,$i$$\lvert h_i(x) \rvert = O(x / (\log x)^2)$
• $x_0$ jest stałą

Zauważ, że , a jako funkcja piłokształtna ma zawsze wartość od 0 do 1, zastępując (lub odpowiednio) spełnia warunki na .$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$\{ u \} = u - \lfloor u \rfloor$$\lfloor b_i x \rfloor$$\lceil b_i x \rceil$$h_i$

Znajdź taki sposób, że: Następnie zachowanie asymptotyczne jako podaje: z „wystarczająco dużym”, tzn. , aby dla wszystkich .$p$

$$\sum_{1 \le i \le k} a_i b_i^p = 1$$ $T(x)$$x \rightarrow \infty$ $$T(x) = \Theta \left( x^p \left( 1 + \int_{x_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$ $x_1$$k_1>0$ $$g(x/2) \geq k_1g(x) \tag{2}$$ $x>x_1$

Przykład A

Jako przykład weźmy rekurencję dla , gdzie : Warunki są spełnione, potrzebujemy : Na szczęście, . Mamy więc: $n \ge 5$$T(0) = T(1) = T(2) = T(3) = T(4) = 17$

$$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ $p$ $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ $p = 2$ $$T(n) = \Theta \left( n^2 \left(1 + \int_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

ponieważ z spełniamy dla wszystkich . Zauważ, że ponieważ całka jest zbieżna, nawet jeśli użyjemy innych stałych, takich jak , jako dolnej granicy, dozwolone jest również ich stosowanie; różnica znika w .$k_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$$(2)$$x\geq 3$$1$$\Theta$

Przykład B

Kolejny przykład jest następujący dla : Mamy sprawdź. Mamy, że istnieje jeden , , który się sprawdza. Zakładając, że jest naprawdę i / lub , domyślny również się sprawdza. Potrzebujemy więc: Zatem i: $n \ge 2$

$$T(n) = 4 T(n / 2) + n^2 / \lg n$$ $g(n) = n^2 / \ln n = O(n^2)$$a_1 = 4$$b_1 = 1 / 2$$n / 2$$\lfloor n / 2 \rfloor$$\lceil n / 2 \rceil$$h_i(n)$ $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ $p = 2$ $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ Stosujemy podobną sztuczkę jak powyżej dolna granica całki, tyle że używamy ponieważ całka nie zbiega się dla .$2$$1$

(Z wdzięcznością przyjmuje się pomoc maksimów z algebrą)

Podsumowania

Często napotyka się nawrót postaci gdzie jest monotoniczny. W tym przypadku możemy rozwinąć a więc biorąc pod uwagę wartość początkową , w celu oszacowania musimy oszacować sumę .

$$T(n) = T(n-1) + f(n),$$ $f(n)$ $$T(n) = T(c) + \sum_{m=c+1}^n f(m),$$ $T(c)$$T(n)$$f(c+1) + \cdots + f(m)$

Nie malejące$f(n)$

Kiedy jest monotoniczny, nie zmniejsza się, mamy oczywiste granice Granice te są najlepiej możliwe w tym sensie, że są ciasne dla niektórych funkcji: górna granica dla funkcji stałych, a dolna granica dla funkcji krokowych ( dla i dla ). Jednak w wielu przypadkach szacunki te nie są bardzo pomocne. Na przykład, gdy , dolna granica to a górna granica to , więc są one dość daleko od siebie.$f(n)$

$$f(n) \leq \sum_{m=c+1}^n f(m) \leq (n-c) f(n).$$ $f(m) = 1$$m \geq n$$f(m) = 0$$m < n$$f(m) = m$$n$$(n-c)n$

Integracja

Lepsze oszacowanie daje integracja: Dla daje to poprawną wartość sumy do niższych wartości: Gdy możemy obliczyć sumę jawnie, ale w wielu przypadkach jawne obliczenia są trudne. Na przykład, gdy pierwotną funkcją jest , a więc

$$\int_c^n f(x) dx \leq \sum_{m=c+1}^n f(m) \leq \int_{c+1}^{n+1} f(x) dx.$$ $f(m) = m$ $$\frac{1}{2} n^2 - \frac{1}{2} c^2 \leq \sum_{m=c+1}^n m \leq \frac{1}{2} (n+1)^2 - \frac{1}{2} (c+1)^2.$$ $f(m) = m$$f(m) = m\log m$$f$$(1/2) x^2\log x - (1/4) x^2$ $$\sum_{m=c+1}^n m\log m = \frac{1}{2} n^2 \log n \pm \Theta(n^2).$$

Wzór Eulera-Maclaurina daje lepsze szacunki. Ta formuła może być użyta na przykład do udowodnienia silnych form formuły Stirlinga poprzez oszacowanie sumy .$\log n! = \sum_{m=1}^n \log m$

Nie rosnąca$f(n)$

W niektórych przypadkach jest monotoniczny. Trywialne oszacowania stają się a całkowite oszacowania Na przykład dla , używając , otrzymujemy $f(n)$

$$f(1) \leq \sum_{m=c+1}^n f(m) \leq (n-c) f(1),$$ $$\int_{c+1}^{n+1} f(x) dx \leq \sum_{m=c+1}^n f(m) \leq \int_c^n f(x) dx.$$ $f(m) = 1/m$$\int f(m) = \log m$ $$\sum_{m=c+1}^n \frac{1}{m} = \log n \pm \Theta(1).$$

Sedgewick i Flajolet wykonali szeroko zakrojone prace w kombinatoryce analitycznej , która umożliwia asymptotyczne rozwiązywanie nawrotów za pomocą kombinacji funkcji generujących i złożonej analizy. Ich praca pozwala na automatyczne rozwiązanie wielu nawrotów i została zaimplementowana w niektórych systemach algebry komputerowej.

Ten podręcznik na ten temat został napisany przez Flajoleta i Sedgewicka i stanowi doskonałe odniesienie. Nieco prostszą ekspozycją dotyczącą aplikacji do analizy algorytmów jest ten tekst autorstwa Sedgewick i Flajolet.

Mam nadzieję że to pomoże!

Może się zdarzyć, że natrafisz na dziwną powtarzalność: Jeśli jesteś podobny do mnie, zdasz sobie sprawę, że nie możesz użyć Twierdzenia Nadrzędnego i wtedy możesz pomyśleć: hmmm ... może analiza drzewa rekurencyjnego mogłaby zadziałać. " Wtedy zdasz sobie sprawę, że drzewo zaczyna naprawdę bardzo szybko rosnąć. Po kilku wyszukiwaniach w Internecie zobaczysz, że metoda Akra-Bazzi będzie działać! Wtedy faktycznie zaczynasz się temu przyglądać i zdajesz sobie sprawę, że tak naprawdę nie chcesz robić całej matematyki. Jeśli do tej pory byłeś taki jak ja, będziesz podekscytowany, wiedząc, że istnieje łatwiejszy sposób.

$$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$

---

Twierdzenie o nierównym podziale Część 1

Niech i będą dodatnimi stałymi.$c$$k$

Niech więc będą dodatnimi stałymi, tak że .$\{a_1, a_2, \ldots, a_k\}$$\sum_1^k a_i < 1$

Musimy także mieć powtarzalność formularza (jak w naszym przykładzie powyżej):

$$\begin{align} T(n) & \leq c & 0 < n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \end{align}$$

Roszczenie

Następnie twierdzę, że gdzie jest stałą (np. Asymptotycznie liniową) i:$T(n) \leq bn$$b$

$$b = \frac{c}{1 - \left(\sum_1^k a_i\right)}$$

Dowód indukcji

Podstawa :$n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \implies T(n) \leq c < b < bn$

Indukcja : Załóżmy, że prawda dla dowolnego , mamy$n' < n$

$$\begin{align} T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\ & \leq cn + b \lfloor a_1 n \rfloor + b \lfloor a_2 n \rfloor + \dots + b \lfloor a_k n \rfloor\\ & \leq cn + b a_1 n + b a_2 n + \dots + b a_k n\\ & = cn + bn \sum_1^k a_i\\[0.5em] & = \frac{cn - cn \sum_1^k a_i }{1 - \left(\sum_1^k a_i\right)} + \frac{cn \sum_1^k a_i}{1 - \left(\sum_1^k a_i\right)}\\[0.5em] & = \frac{cn}{1 - \left(\sum_1^k a_i\right)}\\ & = bn & \square \end{align}$$

Następnie mamy .$T(n) \leq bn \implies T(n) = O(n)$

Przykład

$$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ Najpierw weryfikujemy współczynniki wewnątrz sumy wywołań rekurencyjnych na mniej niż jeden: $$\begin{align} 1 & > \sum_1^k a_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7}\\[0.5em] & = \frac{2}{5} + \frac{4}{7}\\[0.5em] & = \frac{34}{35} \end{align}$$

Następnie sprawdzamy, czy przypadek podstawowy jest mniejszy niż maksimum odwrotności współczynników:

$$\begin{align} n & < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ & = \max\{5, 5, 7, 7, 7, 7\}\\ & = 7 \end{align}$$

Po spełnieniu tych warunków wiemy, że gdzie jest stałą równą: Dlatego mamy: $T(n) \leq bn$$b$

$$\begin{align} b &= \frac{c}{1 - \left(\sum_1^k a_i\right)}\\[0.5em] &= \frac{c}{1 - \frac{34}{35}}\\[0.5em] &= 35c \end{align}$$ $$\begin{align} T(n) & \leq 35cn\\ \land\; T(n) & \geq cn\\ \therefore T(n) & = \Theta(n) \end{align}$$

---

Twierdzenie o nierównym podziale Część 2

Podobnie możemy udowodnić, że kiedy . Dowód będzie zgodny z tym samym formatem:$\sum_1^k = 1$

Niech i będą dodatnimi stałymi takimi, że .$c$$k$$k > 1$

Niech więc będą dodatnimi stałymi, tak że .$\{a_1, a_2, \ldots, a_k\}$$\sum_1^k a_i = 1$

Musimy także mieć powtarzalność formularza (jak w naszym przykładzie powyżej):

$$\begin{align} T(n) & \leq c & 0 < n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ T(n) & \leq cn + T(a_1 n) + T(a_2 n) + \dots T(a_k n) & n \geq \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \end{align}$$

Roszczenie

Następnie twierdzę, że (wybieramy base ponieważ będzie czynnikiem rozgałęziającym drzewa rekurencji), gdzie i są stałymi (np. Asymptotycznie liniowo ) takie, że:$T(n) \leq \alpha n \log_k n + \beta n$$\log$$k$$k$$\alpha$$\beta$

$$\beta = c$$ oraz $$\alpha = \frac{c}{\sum_1^k a_i \log_k a_i^{-1}}$$

Dowód indukcji

Podstawa :$n < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\} \implies T(n) \leq c = \beta < \alpha n \log_k n + \beta n$

Indukcja : Załóżmy, że prawda dla dowolnego , mamy$n' < n$

$$\begin{align} T(n) & \leq cn + T(\lfloor a_1 n \rfloor) + T(\lfloor a_2 n \rfloor) + \dots + T(\lfloor a_k n \rfloor)\\ & \leq cn + \sum_1^k (\alpha a_i n \log_k a_i n + \beta a_i n)\\ & = cn + \alpha n\sum_1^k (a_i \log_k a_i n) + \beta n\sum_1^k a_i\\ & = cn + \alpha n\sum_1^k \left(a_i \log_k \frac{n}{a_i^{-1}}\right) + \beta n\\ & = cn + \alpha n\sum_1^k (a_i (\log_k n - \log_k a_i^{-1})) + \beta n\\ & = cn + \alpha n\sum_1^k a_i \log_k n - \alpha n\sum_1^k a_i \log_k a_i^{-1} + \beta n\\ & = \alpha n\sum_1^k a_i \log_k n + \beta n\\ & = \alpha n \log_k n + \beta n & \square \end{align}$$

Następnie mamy .$T(n) \leq \alpha n \log_k n + \beta n \implies T(n) = O(n \log n)$

Przykład

Zmodyfikujmy poprzedni przykład, którego użyliśmy tylko trochę:

$$T(n) = \begin{cases} c & n < 35\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + T\left(\frac{n}{35}\right)+ cn & n \geq 35 \end{cases}$$

Najpierw weryfikujemy współczynniki wewnątrz rekurencyjnych wywołań do jednego:

$$\begin{align} 1 & = \sum_1^k a_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{35}\\[0.5em] & = \frac{2}{5} + \frac{4}{7} + \frac{1}{35}\\[0.5em] & = \frac{35}{35} \end{align}$$

Następnie sprawdzamy, czy przypadek podstawowy jest mniejszy niż maksimum odwrotności współczynników:

$$\begin{align} n & < \max\{a_1^{-1}, a_2^{-1}, \ldots, a_k^{-1}\}\\ & = \max\{5, 5, 7, 7, 7, 7, 35\}\\ & = 35 \end{align}$$

Po spełnieniu tych warunków wiemy, że gdzie i jest stałą równą: Dlatego mamy: $T(n)\leq \alpha n \log n + \beta n$$\beta = c$$\alpha$

$$\begin{align} b &= \frac{c}{\sum_1^k a_i \log_k a_i^{-1}}\\[0.5em] &= \frac{c}{\frac{2 \log_7 5}{5} + \frac{4 \log_7 7}{7} + \frac{\log_7 35}{35}}\\[0.5em] &\approx 1.048c \end{align}$$ $$\begin{align} T(n) & \leq 1.048cn\log_7 n + cn\\ \therefore T(n) & = O(n \log n) \end{align}$$

Po ponownym sprawdzeniu tego postu jestem zaskoczony, że jeszcze go tu nie ma.

Transformacja domen / zmiana zmiennych

Podczas radzenia sobie z nawrotami czasami przydatna jest możliwość zmiany domeny, jeśli nie jest jasne, jak głęboko sięgnie stos rekurencyjny.

Na przykład weź następujący cykl:

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

Jak moglibyśmy to kiedykolwiek rozwiązać? Moglibyśmy rozszerzyć tę serię, ale obiecuję, że będzie to bardzo szybko obrzydliwe. Zamiast tego zastanówmy się, jak nasze dane wejściowe zmieniają się przy każdym połączeniu.

Najpierw mamy:

1. $n$ , a następnie
2. $2^{2^{\sqrt{\log \log n}}}$ , a następnie
3. $2^{2^{\sqrt{\log \log (2^{2^{\sqrt{\log \log n}}})}}}$ i tak dalej.

Celem transformacji domeny będzie teraz zmiana naszej rekurencji na równoważną tak, że zamiast powyższych przejść, mamy po prostu .$S(k)$$k, k-1, k-2, \ldots$

Na przykład, jeśli pozwolimy , wówczas otrzymamy to za powyższe powtórzenie: Następnie możemy po prostu przepisać go następująco: Następnie wystarczy przekonwertować powrotem na aby uzyskać: $n = 2^{2^{2^{2^k}}}$

$$\begin{align*} T(2^{2^{2^{2^k}}}) & = T(2^{2^{\sqrt{\log \log 2^{2^{2^{2^{k}}}}}}}) + \log \log \log (2^{2^{2^{2^{k}}}})\\ & = T(2^{2^{2^{2^{k-1}}}}) + 2^k \end{align*}$$ $$T(k) = T(k-1) + 2^k = \sum_{i = 1}^{k} 2^k = 2^{k+1} - 1$$ $k$$n$ $$T(n) = 2^{(\log \log \log \log n) + 1} - 1 = O(\log \log \log n)$$

---

W tym przykładzie możemy teraz zobaczyć nasz cel.

Załóżmy, że Dla niektórych stałych i funkcje i .

$$T(n) = \begin{cases} h(1) & n = 1\\ a\cdot T(f(n)) + h(n) & \mathrm{otherwise} \end{cases}$$ $a$$f(n)$$h(n)$

Próbujemy teraz znaleźć funkcję oraz taką że $g(k) = n$$f(g(k)) = g(k-1)$

$$\begin{align*} T(g(k)) &= aT(f(g(k))) + h(g(k))\\ & = a\cdot T(g(k-1)) + h(g(k)) \end{align*}$$

Mówiąc bardziej ogólnie, chcemy gdzie to wielokrotne zastosowanie na , razy. (np. ). Umożliwi to działanie jako funkcja „iteracji”. Gdzie, na głębokości rekurencji, wykonaną pracą jest po prostu .$f^{(i)}(n) = g(k - i)$$f^{(i)}(n)$$f$$n$$i$$f^{(2)}(n) = f(f(n))$$g(k)$$i$$h(g(k-i))$

Następnie możemy łatwo przekonwertować to na , aby Wtedy musimy się tylko martwić sumując dla wszystkich do danego przypadku podstawowego. Oznacza to, że $S(k) = T(g(k))$

$$S(k) = a\cdot S(k-1) + h(g(k))$$ $h(g(k))$$k$ $$S(k) = \sum_{i = g^{-1}(1)}^{k} a^{k - i} h(g(i))$$

Jeśli możemy określić dla niektórych funkcji zamkniętych , wówczas możemy wyznaczyć jako $S(k) = \gamma(k)$$\gamma$$T(n)$

$$T(n) = \gamma( g^{-1}(n))$$

Następnie używamy tego, aby uzyskać ograniczenie na za pomocą jednej z innych metod powyżej. Możesz oczywiście nieco zmodyfikować tę metodę zgodnie ze specyfikacją, ale ogólnie próbujesz znaleźć funkcję iteracyjną aby zmienić w prostą rekurencję.$T(n)$$g(k)$$T(n)$

Nie znam dokładnego sposobu określenia w tym momencie, ale będę nadal o tym myśleć i aktualizować, jeśli stanie się bardziej zrozumiały (lub jeśli jakiś komentator ma jakieś wskazówki!). Moje funkcje przeważnie znajdowałem w przeszłości metodą prób i błędów (przykłady można znaleźć tutaj , tutaj , tutaj i tutaj ).$g(k)$$g(k)$

Jest jeszcze jedno podejście, które działa na proste relacje nawrotów: poproś Wolfram Alpha o rozwiązanie problemu nawrotów.

Na przykład spróbuj wpisać f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)Wolfram Alpha. Otrzymasz rozwiązanie z linkiem do liczb Fibonacciego. Albo spróbować f(1)=1, f(n)=f(n-1)+nlub f(1)=1, f(n)=2*f(n-1)+3*nlub f(n)=f(n-1) + 2 f(n-2), f(1)=1, f(2)=3innych przykładów. Ostrzegamy jednak: Wolfram Alpha może rozwiązać niektóre bardzo proste nawroty, ale rozpada się na bardziej złożone.

Takie podejście pozwala uniknąć jakiegokolwiek myślenia, które może być postrzegane jako błąd lub funkcja.

Przypadek 2 twierdzenia głównego, jak zwykle stwierdzono, obsługuje tylko rekurencje postaci w których dla . Poniższe twierdzenie zaczerpnięte z materiałów Jeffreya Leona daje odpowiedź na ujemne :$T(n) = aT(n/b) + f(n)$$f(n) = \Theta(n^{\log_ab}\log^k n)$$k \geq 0$$k$

Rozważ wznowienie z odpowiednim przypadkiem podstawowym.$T(n) = a T(n/b) + f(n)$

1. Jeśli dla to .$f(n) = O(n^{\log_b a} \log^{c-1} n)$$c < 0$$T(n) = \Theta(n^{\log_b a})$

2. Jeśli dla to .$f(n) = \Theta(n^{\log_b a} \log^{c-1} n)$$c = 0$$T(n) = \Theta(n^{\log_b a} \log\log n)$

3. Jeśli dla to ).$f(n) = \Theta(n^{\log_b a} \log^{c-1} n)$$c > 0$$T(n) = \Theta(n^{\log_b a} \log^c n$

Dowód wykorzystuje metodę wielokrotnego podstawiania, jak teraz szkicujemy. Załóżmy, że oraz . Następnie dla potęga , Rozważmy teraz kolejno przypadki. Gdy , szereg zbiega się, a więc . Gdy , suma jest sumą harmoniczną i tak$f(n) = n^{\log_b a} \log_b^{c-1} n$$T(1) = 0$$n$$b$

$$T(n) = \sum_{i=0}^{\log_b n-1} a^i (nb^{-i})^{\log_b a} \log_b^{c-1} (nb^{-i}) = \\ \sum_{i=0}^{\log_b n-1} n^{\log_b a} (\log_b n - i)^{c-1} = n^{\log_b a} \sum_{j=1}^{\log_b n} j^{c-1}.$$ $c < 0$$\sum_{j=0}^\infty j^{c-1}$$T(n) = \Theta(n^{\log_b a})$$c = 0$$H_{\log_b n} = \log(\log_b n) + O(1)$$T(n) = \Theta(n^{\log_b a} \log \log n)$ . Gdy , możemy przybliżać sumę za pomocą całki: a więc .$c > 0$ $$\sum_{j=1}^{\log_b n} \approx \int_0^{\log_b n} x^{c-1} \, dx = \left. \frac{x^c}{c} \right|_0^{\log_b n} = \frac{\log_b^c n}{c},$$ $T(n) = \Theta(n^{\log_b a} \log^c n)$