Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb


89

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

    T(0)=0T(n+1)=T(n)+f(n)

  2. Sekwencja Fibonacciego :

    F0=0F1=1Fn+2=Fn+Fn+1

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

    C0=1Cn+1=i=0nCiCni

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

    T(1)=T(0)=0T(n)=T(n/2)+T(n/2)+n1

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.


9
Te notatki mogą być pomocne. (Ale nie, nie
podzielę

Odpowiedzi:


35

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<n

T(n)=n+1nk=1n(T(k1)+T(nk))
knT(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 )

nT(n)=n2+2k=1n1T(k)
T(n1)
(n1)T(n1)=(n1)2+2k=1n2T(k)nT(n)(n1)T(n1)=(2n1)+2T(n1)nT(n)=(2n1)+(n+1)T(n1)T(n)n+1=2n1n(n+1)+T(n1)n

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 - 1t(n)=T(n)/(n+1) Θ(1/n)t(n)=Θ(1/n)+t(n-1). t(n)=Θ(Hn)=Θ(logn)Hnn2n1n(n+1)Θ(1/n)

t(n)=Θ(1/n)+t(n1).
t(n)=Θ(Hn)=Θ(logn)HnnT(n)=Θ(nlogn)

1
Jeśli chcesz precyzyjnego rozwiązania dla , nie jest to również trudne (tutaj), choć trochę nudne; otrzymujemy . Właściwie myli mnie, więc wolę dokładny wariant. Pesky sumy warunków Landau . T ( n ) = 2 ( n + 1 ) H n + ( T ( 0 ) - 3 ) n + T ( 0 ) n i = 1 Θ ( 1 / i ) = Θ ( H n )TT(n)=2(n+1)Hn+(T(0)3)n+T(0)i=1nΘ(1/i)=Θ(Hn)
Raphael

W rzeczywistości wystarczy zaobserwować (indukcyjnie), że , gdzie . W rzeczywistości użyłem tej sztuczki już na samym początku, kiedy zastąpiłem czas aby podzielić tablicę na prostszą . Jest to całkowicie standardowe nadużycie notacji. t ( n ) = 1 / n + t ( n - 1 ) Θ ( n ) nT(n)/(n+1)=Θ(t(n))t(n)=1/n+t(n1)Θ(n)n
JeffE

28

Generowanie funkcji

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(an)nN

A(z)=n=0anzn

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(an)nNA(z)[zn]A(z)=an Cn

C(z)=114z2z .

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 powtarzalnaA

a0=c0ak1=ck1an=f(n)+i=1kbiani,nk

dla niektórych stałych i funkcja niezależna od wszystkich . Teraz po prostu wstawiamy zarówno kotwice, jak i część rekurencyjną do ansatzb1,,bkRf(n):NNai

A(z)=n=0anzn=c0z0+c1z1++ck1zk1+n=k[f(n)+(i=1kbiani)]zn

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ć

a0=1a1=2an=5n+3an12an2,n>1

Obliczamy:

A(z)=n=0anzn=1+2z+n=2[3an12an2+5n]zn=1+2z+3n=2an1zn2n=2an2zn+5n=2nzn=1+2z+3zn=1anzn2z2n=0anzn+5n=2nzn=1+2z+3z(A(z)a0)2z2A(z)+5(z(1z)2z)=16z+(3z2z2)A(z)+5z(1z)2

To rozwiązuje

A(z)=13z+13z26z3(12z)(1z)3=1612z51z5(1z)25(1z)3=16n=02nzn5n=0zn5n=0(n+1)zn5n=0(n+1)(n+2)2zn

Teraz możemy wreszcie odczytać

an=162n55(n+1)52(n+1)(n+2)=2n+452n2252n15

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

a0=c0ak1=ck1an=i=1kbiani,nk

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ć

zkb1zk1b2zk2bk

być charakterystycznym wielomianem (nawrotu). Niech ponadto (odrębne parami) zera wspomnianego wielomianu o wielokrotności odpowiednio . Następnie żądany współczynnik podajeλ1,,λlri

an=i=1lj=1ribi,jnj1λin

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).bi,jkkrikkkan

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

21

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:

T(n)=aT(nb)+f(n)

z . Istnieją trzy przypadkia1,b>1

  1. fO(nlogb(a)ε)

    dla niektórych ;ε>0

  2. fΘ(nlogbalogkn) ,

    dla niektórych ;k0

  3. fΩ(nlogb(a)+ε)

    dla niektórych iε>0

    af(nb)cf(n)

    dla niektórych i .c<1n

co implikuje asymptotyki

  1. TΘ(nlogba) ,
  2. TΘ(nlogbalogk+1n) i
  3. TΘ(f) ,

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 .Θ

Przykłady

  1. Rozważ powtórzenie

    T(n)=4T(n3)+n .

    Przy i - zwróć uwagę, że widzimy, że przypadek 1 dotyczy . Dlatego .f(n)=n,a=4b=3logba1.26ε=0.25TΘ(nlog34)=Θ(n1.261)

  2. Rozważ powtórzenie

    T(n)=2T(n/2)+n .

    Przy i - zwróć uwagę, że widzimy, że drugi przypadek dotyczy . Dlatego .f(n)=n,a=2b=2logba=1k=0TΘ(nlogn)

  3. Rozważ powtórzenie

    T(n)=3T(n4)+n .

    Z , a - Uwaga widzimy, że stosuje się w przypadku trzy i . Dlatego .f(n)=n,a=3b=4logba0.79ε=0.2c=1TΘ(n)

  4. Rozważ powtórzenie

    T(n)=16T(n4)+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=16b=4f(n)=n!flogba=2εc>0n!Ω(nk)kTΘ(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=bk


  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)

To może być głupie pytanie, ale często nie utrzymuję modelu mentalnego, gdy a nie jest równe b, nie wiem dlaczego, ale intuicyjnie zawsze czuję, że oba muszą być zawsze takie same, jak w przypadku scalania, dzielimy problem na dwie równe (prawie) połówki i każda z n / 2 instancjami. Ponadto, jeśli podzielimy algorytm na trzy równe części, wówczas dane wejściowe powinny również zostać podzielone na trzy równe części, co ponownie powoduje, że aib są równe. Jak mogę złamać tę błędną intuicję?
CodeYogi

17

Zgadnij i udowodnij

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

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 ( ).

Prosty przykład

s0=s1=s2=1sn=5sn3+6n2

kilka razy definicję :sn

sn=5sn3+6=5(5sn6+6)+6=5(5(5sn9+6)+6)+6 =5(5(5(51n÷3 times+6)+6)+6)+6n÷3 times

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

sn=5n3+6i=0n315i=525n364

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 , obliczamyn{0,1,2}nnn3

sn+3=5sn+6=5(525n364)+6=525n3+164=525n+3364

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=2k

T(1)=T(0)=0T(n)=2T(n/2)+n1n1

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

T(n)=2T(n/2)+n12n2logn2+n1=nlognnlog2+n1<nlogn


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

15

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)=1ikaiT(bix+hi(x))+g(x)for xx0
hi(x)
  • Istnieje wystarczająca liczba przypadków podstawowych, aby rozpocząć nawrót
  • i są stałymiaibi
  • Dla wszystkich ,iai>0
  • Dla wszystkich ,i0<bi<1
  • |g(x)|=O(xc) dla pewnej stałej jakocx
  • Dla wszystkich ,i|hi(x)|=O(x/(logx)2)
  • x0 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 .bix=bix{bix}{u}=uubixbixhi

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

1ikaibip=1
T(x)x
T(x)=Θ(xp(1+x1xg(u)up+1du))
x1k1>0
(2)g(x/2)k1g(x)
x>x1

Przykład A

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

T(n)=9T(n/5)+T(4n/5)+3nlogn
p
9(15)p+(45)p=1
p=2
T(n)=Θ(n2(1+3n3uloguu3du))=Θ(n2)

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 .k112(1log2log3)(2)x31Θ

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: n2

T(n)=4T(n/2)+n2/lgn
g(n)=n2/lnn=O(n2)a1=4b1=1/2n/2n/2n/2hi(n)
a1b1p=4(1/2)p=1
p=2
T(n)=Θ(n2(1+2nu2duu3lnu))=Θ(n2(1+2nduulnu))=Θ(n2lnlnn)
Stosujemy podobną sztuczkę jak powyżej dolna granica całki, tyle że używamy ponieważ całka nie zbiega się dla .21

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


1
Sprawdziłem oryginalny papier. Mają techniczne ograniczenie dolnej granicy całki; twoja wersja (powołując się na ankietę Mehlhorna?) wyraźnie wymaga zbieżności całki. Ponieważ uważam, że łatwiej jest sprawdzić oryginalny stan, odpowiednio zmieniłem oświadczenie i przykłady, proszę sprawdzić.
Raphael

1
Co więcej, oryginalny artykuł nie podaje wersji z ; czy jest to zaczerpnięte z rękopisu Leightona? Czy masz na to recenzowane referencje? Czy powinniśmy przejść do wersji podanej w artykule z 1998 roku autorstwa Akra & Bazzi? hi
Raphael

1
Natknąłem się na coś, co wydaje się niespójne w tym twierdzeniu . Może znasz odpowiedź?
Raphael

11

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(n1)+f(n),
f(n)
T(n)=T(c)+m=c+1nf(m),
T(c)T(n)f(c+1)++f(m)

Nie malejącef(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)m=c+1nf(m)(nc)f(n).
f(m)=1mnf(m)=0m<nf(m)=mn(nc)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

cnf(x)dxm=c+1nf(m)c+1n+1f(x)dx.
f(m)=m
12n212c2m=c+1nm12(n+1)212(c+1)2.
f(m)=mf(m)=mlogmf(1/2)x2logx(1/4)x2
m=c+1nmlogm=12n2logn±Θ(n2).

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 .logn!=m=1nlogm

Nie rosnącaf(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)m=c+1nf(m)(nc)f(1),
c+1n+1f(x)dxm=c+1nf(m)cnf(x)dx.
f(m)=1/mf(m)=logm
m=c+1n1m=logn±Θ(1).

Ta odpowiedź w mniejszym stopniu dotyczy rozwiązywania nawrotów, ale raczej szacowania sum (co może być przydatne w rozwiązywaniu nawrotów); technika jest podwójna z sum Riemanna . Powinien także współpracować z innymi formami, takimi jak dla stałej ? T(nd)d
Raphael

W prawo, można również rozwiązać w ten sposób. T(n)=cT(nd)+f(n)
Yuval Filmus,

9

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!


4
To miłe odniesienie, ale chcemy zbierać metody w przystępny sposób. Czy możesz szczegółowo przedstawić jedną konkretną metodę?
Raphael

9

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.