Hovedsætning om gentagelsesrelationer

Mastersætningen bruges i analysen af algoritmer til at opnå et asymptotisk estimat for rekursive relationer ( rekursive ligninger ), som ofte opstår i analysen af algoritmer af typen " divide and conquer " ( divide and conquer ), for eksempel ved estimering deres udførelsestid. Sætningen blev introduceret og bevist af John Bentley, Doroten Haken og James Haken i 1980. Sætningen blev populariseret i bogen Algorithms: Construction and Analysis ( Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein ), hvori den blev givet.

Ikke alle rekursive relationer kan løses ved hjælp af hovedsætningen. Der er flere generaliseringer af det, herunder Akra-Bazzi-metoden .

Beskrivelse

Overvej et problem, der kan løses med en rekursiv algoritme :

funktion T(input n : opgavestørrelse): hvis n < en eller anden konstant k : løs problemet for n ikke-rekursivt ellers :definere et sæt af underopgaver, hver af størrelse n/b kalde funktion T rekursivt for hver delopgave kombinere løsninger ende

I ovenstående eksempel opdeler algoritmen rekursivt den oprindelige opgave af størrelse n i flere nye underopgaver, hver af størrelse n/b . En sådan partition kan repræsenteres som et opkaldstræ, hvor hver node svarer til et rekursivt opkald, og grene, der udgår fra noden, svarer til efterfølgende opkald til underopgaver. Hver knude vil have en gren. Hver node producerer også den mængde arbejde, der svarer til størrelsen af den aktuelle underopgave n (overført til dette funktionskald) i henhold til relationen . Algoritmens samlede mængde arbejde er defineret som summen af alt arbejdet i knuderne i det givne træ. $f(n)$

Den beregningsmæssige kompleksitet af sådanne algoritmer kan repræsenteres som en rekursiv relation . Det kan løses ved flere substitutioner af udtrykket . [en] $T(n)=a\;T\venstre({\frac {n}{b}}\right)+f(n)$ $T\venstre({\frac {n}{b}}\højre)$

Ved hjælp af hovedsætningen er det muligt hurtigt at beregne sådanne relationer, hvilket gør det muligt at opnå et asymptotisk estimat af køretiden for rekursive algoritmer i O(n) -notationen (Θ-notationen) uden substitutioner.

Generel form

Hovedsætningen overvejer følgende gentagelsesrelationer:

T(n)=a\;T\!\left({\frac {n}{b))\right)+f(n),\;\;\;\;{\mbox{hvor} }\;\;a\geq 1{\mbox{, }}b>1

Som anvendt til analyse af algoritmer, betyder konstanter og funktioner:

n er opgavestørrelsen.
a er antallet af delopgaver i rekursionen.
n / b er størrelsen af hver delopgave. (Det antages, at alle delopgaver i hvert trin er af samme størrelse.)
f ( n ) er et estimat af kompleksiteten af arbejdet udført af algoritmen uden for rekursive opkald. Det inkluderer også de beregningsmæssige omkostninger ved at opdele i delproblemer og kombinere resultaterne af løsning af delproblemer.

Hovedsætningen giver os mulighed for at opnå et asymptotisk estimat for følgende tre tilfælde:

Mulighed 1

Generel form

Hvis , og forholdet $f(n)=O\venstre(n^{{c}}\højre)$ $c<\log _{b}a$

derefter:

T(n)=\Theta \left(n^{{\log _{b}a}}\right)

Eksempel

T(n)=8T\venstre({\frac {n}{2}}\right)+1000n^{2}

Ifølge formlen er værdierne af konstanterne og kompleksiteten af den ikke-rekursive del af problemet:

a=8,\,b=2,\,f(n)=1000n^{2}

f(n)=O\venstre(n^{c}\højre)

, hvor

c=2

Derefter kontrollerer vi, om forholdet til 1. mulighed er opfyldt:

\log _{b}a=\log _{2}8=3>c

Følgelig,

T(n)=\Theta \left(n^{{\log _{b}a}}\right)=\Theta \left(n^{{3}}\right)

(For dette eksempel giver den nøjagtige gentagelsesløsning , forudsat ). $T(n)=1001n^{3}-1000n^{2}$ $T(1)=1$

Mulighed 2

Generel form

Hvis for en eller anden konstant k ≥ 0 gælder følgende:

f(n)=\Theta \left(n^{{c}}\log ^{{k}}n\right)

hvor

c=\log _{b}a

derefter:

T(n)=\Theta \left(n^{{c}}\log ^{{k+1}}n\right)

Eksempel

$T(n)=2T\venstre({\frac {n}{2}}\højre)+10n$

Ifølge formlen er værdierne af konstanterne og kompleksiteten af den ikke-rekursive del af problemet:

a=2,\,b=2,\,c=1,\,f(n)=10n

f(n)=\Theta \left(n^{{c}}\log ^{{k}}n\right)

hvor

c=l,k=0

Kontrol af forholdet mellem mulighed 2:

\log _{b}a=\log _{2}2=1

, og dermed

c=\log _{b}a

I overensstemmelse med 2. version af hovedsætningen:

T(n)=\Theta \left(n^{{\log _{b}a}}\log ^{{k+1}}n\right)=\Theta \left(n^{{1}} \log ^{{1}}n\right)=\Theta \left(n\log n\right)

Således er gentagelsesrelationen T ( n ) Θ( n log n ).

(Dette resultat kan verificeres ved den nøjagtige løsning af forholdet, hvori , med forbehold for .) $T(n)=n+10n\log _{2}n$ $T(1)=1$

Mulighed 3

Generel form

Hvis udført:

f(n)=\Omega \venstre(n^{{c}}\højre)

hvor

c>\log _{b}a

og det er også rigtigt, at:

af\left({\frac {n}{b}}\right)\leq kf(n)

for nogle konstante og store nok (den såkaldte regularitetstilstand )

k<1

n

derefter:

T\venstre(n\højre)=\Theta\venstre(f(n)\højre)

Eksempel

T(n)=2T\venstre({\frac {n}{2}}\højre)+n^{2}

Konstante værdier og funktioner:

a=2,\,b=2,\,f(n)=n^{2}

f(n)=\Omega \venstre(n^{c}\højre)

, hvor

c=2

Vi kontrollerer, at forholdet fra mulighed 3 er opfyldt:

\log _{b}a=\log _{2}2=1

, og dermed

c>\log _{b}a

Regelmæssighedsbetingelsen gælder også :

2\venstre({\frac {n^{2}}{4}}\højre)\leq kn^{2}

, når du vælger

k=1/2

Derfor, ifølge den 3. version af hovedsætningen:

T\left(n\right)=\Theta \left(f(n)\right)=\Theta \left(n^{2}\right).

Denne rekursive relation T ( n ) er lig med Θ( n 2 ), hvilket er det samme som f ( n ) i den oprindelige formel.

(Dette resultat bekræftes af den nøjagtige gentagelsesløsning, hvor , med forbehold for .) $T(n)=2n^{2}-n$ $T(1)=1$

Udtryk, der ikke er løst af hovedsætningen

Følgende relationer kan ikke løses ved hjælp af hovedsætningen: [2]

$T(n)=2^{n}T\venstre({\frac {n}{2}}\right)+n^{n}$ a er ikke en konstant, hovedsætningen kræver et konstant antal delopgaver;
$T(n)=2T\venstre({\frac {n}{2}}\right)+{\frac {n}{\log n}}$ mellem f(n) og der er en ikke-polynomiel afhængighed; $n^{{\log _{b}a}}$
$T(n)=0,5T\venstre({\frac {n}{2}}\højre)+n$ a < 1, men hovedsætningen kræver mindst én delopgave;
$T(n)=64T\venstre({\frac {n}{8}}\højre)-n^{2}\log n$ f(n) er negativ;
$T(n)=T\venstre({\frac {n}{2}}\right)+n(2-\cos n)$ tæt på mulighed 3, men regelmæssighedsbetingelsen er ikke opfyldt .

I det andet eksempel kan forskellen mellem og udtrykkes som . Det viser, at for enhver konstant . Derfor er forskellen ikke et polynomium, og hovedsætningen gælder ikke. $f(n)$ $n^{{\log _{b}a}}$ ${\frac {f(n)}{n^{{\log _{b}a))))={\frac ({\frac {n}{\log n))}{n^{{log_{ 2}2))))={\frac {n}{n\log n}}={\frac {1}{\log n}}$ ${\frac {1}{\log n}}<n^{\epsilon }$ $\epsilon > 0$

Anvendelse til nogle algoritmer

Algoritme	Tilbagevendende forhold	Arbejdstimer	Bemærk
Binær søgning	$T(n)=T\venstre({\frac {n}{2}}\højre)+O(1)$	$O(\log n)$	Hovedsætning, 2. mulighed: , hvor [3] $c=\log _{b}a$ $a=1,b=2,c=0,k=0$
Binær trægennemgang	$T(n)=2T\venstre({\frac {n}{2}}\højre)+O(1)$	$På)$	Hovedsætning, version 1: hvor [3] $c<\log _{b}a$ $a=2,b=2,c=0$
Strassen algoritme	$T(n)=7T\venstre({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\approx O(n^{2.81})$	Hovedsætning, version 1: , hvor [4] $c<\log _{b}a$ $a=7,b=2,c=2$
Optimal Sorteret Matrix-søgning	$T(n)=2T\venstre({\frac {n}{2}}\højre)+O(\log n)$	$På)$	Akra-Bazzi teorem for og for at få $p=1$ $g(u)=\log(u)$ $\Theta (2n-\log n)$
Flet sortering	$T(n)=2T\venstre({\frac {n}{2}}\højre)+O(n)$	$O(n\log n)$	Hovedsætning, 2. mulighed: , hvor $c=\log _{b}a$ $a=2,b=2,c=1,k=0$

Se også

Akra-Bazzi metode

Noter

↑ Duke University, "Big-Oh for Recurrence Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html Arkiveret 22. juni 2012 på Wayback Machine
↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (dødt link)
↑ 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Arkiveret 21. april 2017 på Wayback Machine
↑ En Master Theorem for Discrete Divide and Conquer-gentagelser . Hentet 19. august 2016. Arkiveret fra originalen 18. april 2016. (ubestemt)

Litteratur

Kormen, T., Leizerson, C., Rivest, R., Stein, C. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . Kapitel 4.3 (hovedsætning) og 4.4 (bevis)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduktion til algoritmer. — 2. - MIT Press og McGraw-Hill, 2001. - ISBN 0-262-53196-8 . Afsnit 4.3 (Mastermetoden) og 4.4 (Bevis for mastersætningen), s. 73-90. (Engelsk)
Michael T. Goodrich og Roberto Tamassia . Algoritmedesign: Fundament-, analyse- og interneteksempler . Wiley, 2002. ISBN 0-471-38365-1 . Hovedsætningen (inklusive versionen af Case 2 inkluderet her, som er stærkere end den fra CLRS) er på s. 268-270. (Engelsk)
KAPITEL 5. REKURSION OG GENTAGELSER 5.2 Mastersætningen arkiveret 21. april 2017 på Wayback Machine , CS 21/Math 19 - Kursusnotater arkiveret 21. juli 2010 på Wayback Machine , Ken Bogart og Cliff Stein: Discrete Math in Computer Science.