Huvudsats om återfallsrelationer

Mastersatsen används vid analys av algoritmer för att erhålla en asymptotisk uppskattning av rekursiva relationer ( rekursiva ekvationer ), som ofta uppstår vid analys av algoritmer av typen " dela och erövra " ( dela och erövra ), till exempel vid skattning deras avrättningstid. Teoremet introducerades och bevisades av John Bentley, Doroten Haken och James Haken 1980. Teoremet populariserades i boken Algorithms : Construction and Analysis ( Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein ) där den gavs.

Alla rekursiva relationer kan inte lösas med hjälp av huvudsatsen. Det finns flera generaliseringar av det, inklusive Akra-Bazzi-metoden .

Beskrivning

Tänk på ett problem som kan lösas med en rekursiv algoritm :

funktion T(ingång n : uppgiftsstorlek): om n < någon konstant k : lös problemet för n icke-rekursivt annars :definiera en uppsättning av deluppgifter, var och en av storlek n/b anropa funktion T rekursivt för varje deluppgift kombinera lösningar slutet

I exemplet ovan delar algoritmen rekursivt upp den ursprungliga uppgiften av storlek n i flera nya deluppgifter, var och en av storleken n/b . En sådan partition kan representeras som ett anropsträd, i vilket varje nod motsvarar ett rekursivt anrop, och grenar som utgår från noden motsvarar efterföljande anrop för deluppgifter. Varje nod kommer att ha en gren. Varje nod producerar också mängden arbete som motsvarar storleken på den aktuella deluppgiften n (som skickas till detta funktionsanrop) enligt relationen . Algoritmens totala mängd arbete definieras som summan av allt arbete i noderna i det givna trädet. $f(n)$

Beräkningskomplexiteten hos sådana algoritmer kan representeras som en rekursiv relation . Det kan lösas genom flera substitutioner av uttrycket . [ett] $T(n)=a\;T\vänster({\frac {n}{b}}\höger)+f(n)$ $T\vänster({\frac {n}{b}}\höger)$

Med hjälp av huvudsatsen är det möjligt att snabbt beräkna sådana samband, vilket gör det möjligt att få en asymptotisk uppskattning av körtiden för rekursiva algoritmer i O(n) -notationen (Θ-notationen) utan substitutioner.

Allmän form

Huvudsatsen tar hänsyn till följande återkommande relationer:

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

Såsom tillämpat på analys av algoritmer, anger konstanter och funktioner:

n är uppgiftens storlek.
a är antalet deluppgifter i rekursionen.
n / b är storleken på varje deluppgift. (Det antas att alla deluppgifter i varje steg är av samma storlek.)
f ( n ) är en uppskattning av komplexiteten i arbetet som utförs av algoritmen utanför rekursiva anrop. Det inkluderar också beräkningskostnaden för att dela upp i delproblem och kombinera resultaten av att lösa delproblem.

Huvudsatsen tillåter oss att få en asymptotisk uppskattning för följande tre fall:

Alternativ 1

Allmän form

Om och förhållandet $f(n)=O\vänster(n^{{c}}\höger)$ $c<\log _{b}a$

sedan:

T(n)=\Theta \left(n^{{\log _{b}a}}\höger)

Exempel

T(n)=8T\vänster({\frac {n}{2}}\höger)+1000n^{2}

Enligt formeln är värdena för konstanterna och komplexiteten hos den icke-rekursiva delen av problemet:

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

f(n)=O\vänster(n^{c}\höger)

, var

c=2

Sedan kontrollerar vi om förhållandet för det första alternativet är uppfyllt:

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

Följaktligen,

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

(För det här exemplet ger den exakta återkommande lösningen , förutsatt ). $T(n)=1001n^{3}-1000n^{2}$ $T(l)=1$

Alternativ 2

Allmän form

Om för någon konstant k ≥ 0 gäller följande:

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

var

c=\log _{b}a

sedan:

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

Exempel

$T(n)=2T\vänster({\frac {n}{2}}\höger)+10n$

Enligt formeln är värdena för konstanterna och komplexiteten hos den icke-rekursiva delen av problemet:

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

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

var

c=l,k=0

Kontrollera förhållandet mellan alternativ 2:

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

, och följaktligen

c=\log _{b}a

I enlighet med den andra versionen av huvudsatsen:

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 är återfallsrelationen T ( n ) Θ( n logn ) .

(Detta resultat kan verifieras genom den exakta lösningen av relationen där , med förbehåll för .) $T(n)=n+10n\log _{2}n$ $T(l)=1$

Alternativ 3

Allmän form

Om det körs:

f(n)=\Omega \left(n^{{c}}\höger)

var

c>\log _{b}a

och det är också sant att:

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

för vissa konstant och tillräckligt stor (det så kallade regularitetstillståndet )

k<1

n

sedan:

T\vänster(n\höger)=\Theta\vänster(f(n)\höger)

Exempel

T(n)=2T\vänster({\frac {n}{2}}\höger)+n^{2}

Konstanta värden och funktioner:

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

f(n)=\Omega \left(n^{c}\right)

, var

c=2

Vi kontrollerar att relationen från alternativ 3 är uppfylld:

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

, och följaktligen

c>\log _{b}a

Regelbundenhetsvillkoret gäller också :

2\left({\frac {n^{2}}{4}}\right)\leq kn^{2}

, när du väljer

k=1/2

Därför, enligt den 3:e versionen av huvudsatsen:

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

Denna rekursiva relation T ( n ) är lika med Θ( n 2 ), vilket är samma som f ( n ) i den ursprungliga formeln.

(Detta resultat bekräftas av den exakta återkommande lösningen där , med förbehåll för .) $T(n)=2n^{2}-n$ $T(l)=1$

Uttryck som inte löses av huvudsatsen

Följande samband kan inte lösas med hjälp av huvudsatsen: [2]

$T(n)=2^{n}T\vänster({\frac {n}{2}}\höger)+n^{n}$ a är inte en konstant, huvudsatsen kräver ett konstant antal delproblem;
$T(n)=2T\vänster({\frac {n}{2}}\höger)+{\frac {n}{\log n}}$ mellan f(n) och det finns ett icke-polynomiskt beroende; $n^{{\log _{b}a}}$
$T(n)=0,5T\vänster({\frac {n}{2}}\höger)+n$ a < 1, men huvudsatsen kräver minst en deluppgift;
$T(n)=64T\vänster({\frac {n}{8}}\höger)-n^{2}\log n$ f(n) är negativ;
$T(n)=T\vänster({\frac {n}{2}}\höger)+n(2-\cos n)$ nära alternativ 3, men regelbundenhetsvillkoret är inte uppfyllt .

I det andra exemplet kan skillnaden mellan och uttryckas som . Det visar att för varje konstant . Därför är skillnaden inte ett polynom och huvudsatsen gäller inte. $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$

Tillämpning på vissa algoritmer

Algoritm	Återkommande relation	Arbetstimmar	Notera
Binär sökning	$T(n)=T\vänster({\frac {n}{2}}\höger)+O(1)$	$O(\log n)$	Huvudsats, 2:a alternativet: , där [3] $c=\log _{b}a$ $a=1,b=2,c=0,k=0$
Binär trädpassering	$T(n)=2T\vänster({\frac {n}{2}}\höger)+O(1)$	$På)$	Huvudsats, version 1: där [3] $c<\log _{b}a$ $a=2,b=2,c=0$
Strassen algoritm	$T(n)=7T\left({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\approx O(n^{2.81})$	Huvudsats, version 1: , där [4] $c<\log _{b}a$ $a=7,b=2,c=2$
Optimal sorterad matrissökning	$T(n)=2T\vänster({\frac {n}{2}}\höger)+O(\log n)$	$På)$	Akra-Bazzi teorem för och för att få $p=1$ $g(u)=\log(u)$ $\Theta (2n-\log n)$
Slå samman sortering	$T(n)=2T\vänster({\frac {n}{2}}\höger)+O(n)$	$O(n\log n)$	Huvudsats, 2:a alternativet: , där $c=\log _{b}a$ $a=2,b=2,c=1,k=0$

Se även

Akra-Bazzi-metoden

Anteckningar

↑ Duke University, "Big-Oh for Recurrive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html Arkiverad 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öd länk)
↑ 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Arkiverad 21 april 2017 på Wayback Machine
↑ En Master Theorem for Discrete Divide and Conquer recurrences . Hämtad 19 augusti 2016. Arkiverad från originalet 18 april 2016. (obestämd)

Litteratur

Kormen, T., Leizerson, C., Rivest, R., Stein, C. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a. - M. : Williams, 2005. - 1296 sid. — ISBN 5-8459-0857-4 . Kapitel 4.3 (huvudsats) och 4.4 (bevis)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduktion till algoritmer. — 2:a. - MIT Press och McGraw-Hill, 2001. - ISBN 0-262-53196-8 . Avsnitt 4.3 (Mästarmetoden) och 4.4 (Bevis för mastersatsen), s. 73-90. (Engelsk)
Michael T. Goodrich och Roberto Tamassia . Algoritmdesign: grund, analys och internetexempel . Wiley, 2002. ISBN 0-471-38365-1 . Mastersatsen (inklusive versionen av fall 2 som ingår här, som är starkare än den från CLRS) finns på sid. 268-270. (Engelsk)
KAPITEL 5. REKURSION OCH RECURSIONER 5.2 Mastersatsen arkiverad 21 april 2017 vid Wayback Machine , CS 21/Math 19 - Kursanteckningar arkiverad 21 juli 2010 vid Wayback Machine , Ken Bogart och Cliff Stein: Discrete Math in Computer Science.