Päälause toistuvuussuhteista

Master-lausetta käytetään algoritmien analysoinnissa asymptoottisen arvion saamiseksi rekursiivisille suhteille ( rekursiiviset yhtälöt ), joita usein syntyy " hajoa ja hallitse " -tyyppisten algoritmien analysoinnissa ( hajoa ja hallitse ) esimerkiksi estimoinnissa niiden toteutusaika. Lauseen esitteli ja todisti John Bentley, Doroten Haken ja James Haken vuonna 1980. Lause levitettiin suosituksi kirjassa Algorithms: Construction and Analysis ( Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein ), jossa se esitettiin.

Kaikkia rekursiivisia suhteita ei voida ratkaista päälauseen avulla. Siitä on useita yleistyksiä, mukaan lukien Akra-Bazzi-menetelmä .

Kuvaus

Harkitse ongelmaa, joka voidaan ratkaista rekursiivisella algoritmilla :

funktio T(syöte n : tehtävän koko): jos n < jokin vakio k : ratkaise n: n tehtävä ei-rekursiivisesti muuten : määritä joukko alitehtäviä, joista jokainen on kooltaan n/b kutsua funktiota T rekursiivisesti jokaiselle osatehtävälle yhdistää ratkaisuja loppu

Yllä olevassa esimerkissä algoritmi jakaa rekursiivisesti alkuperäisen koon n tehtävän useiksi uusiksi alitehtäviksi, joista jokainen on kooltaan n/b . Tällainen osio voidaan esittää puhelupuuna, jossa jokainen solmu vastaa rekursiivista puhelua ja solmusta lähtevät haarat vastaavat myöhempiä alitehtävien kutsuja. Jokaisella solmulla on haarat . Lisäksi jokainen solmu tuottaa nykyisen alitehtävän n kokoa vastaavan määrän työtä (välitetty tälle funktiokutsulle) suhteen mukaan . Algoritmin työn kokonaismäärä määritellään kaiken työn summana annetun puun solmuissa. $f(n)$

Tällaisten algoritmien laskennallinen monimutkaisuus voidaan esittää rekursiivisena relaationa . Se voidaan ratkaista useilla lausekkeen korvauksilla . [yksi] $T(n)=a\;T\left({\frac {n}{b}}\right)+f(n)$ $T\vasen({\frac {n}{b}}\oikea)$

Päälauseen avulla on mahdollista laskea nopeasti sellaiset suhteet, jolloin voidaan saada asymptoottinen arvio rekursiivisten algoritmien ajoajasta O(n) -merkinnässä (Θ-merkintä) ilman substituutioita.

Yleinen lomake

Päälause käsittelee seuraavia toistuvuussuhteita:

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

Algoritmien analysoinnissa vakiot ja funktiot tarkoittavat:

n on tehtävän koko.
a on alitehtävien lukumäärä rekursiossa.
n / b on kunkin alitehtävän koko. (Oletetaan, että kaikki alatehtävät kussakin vaiheessa ovat samankokoisia.)
f ( n ) on arvio algoritmin suorittaman työn monimutkaisuudesta rekursiivisten kutsujen ulkopuolella. Se sisältää myös osaongelmiin jakamisen ja aliongelmien ratkaisutulosten yhdistämisen laskennalliset kustannukset.

Päälause antaa meille mahdollisuuden saada asymptoottinen arvio seuraaville kolmelle tapaukselle:

Vaihtoehto 1

Yleinen lomake

Jos , ja suhde $f(n)=O\vasen(n^{{c}}\oikea)$ $c<\log _{b}a$

sitten:

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

Esimerkki

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

Kaavan mukaan vakioiden arvot ja ongelman ei-rekursiivisen osan monimutkaisuus ovat:

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

f(n)=O\vasen(n^{c}\oikea)

, missä

c = 2

Sitten tarkistamme, täyttyykö 1. vaihtoehdon suhde:

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

Näin ollen

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

(Tässä esimerkissä tarkka toistumisratkaisu antaa , jos ). $T(n)=1001n^{3}-1000n^{2}$ $T(1) = 1$

Vaihtoehto 2

Yleinen lomake

Jos jollekin vakiolle k ≥ 0 pätee seuraava:

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

missä

c=\log _{b}a

sitten:

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

Esimerkki

$T(n)=2T\vasen({\frac {n}{2}}\oikea)+10n$

Kaavan mukaan vakioiden arvot ja ongelman ei-rekursiivisen osan monimutkaisuus ovat:

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

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

missä

c = 1, k = 0

Vaihtoehdon 2 suhteen tarkistaminen:

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

, ja siten

c=\log _{b}a

Päälauseen toisen version mukaisesti:

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)

Siten toistuvuusrelaatio T ( n ) on Θ( n log n ).

(Tämä tulos voidaan varmistaa sen suhteen tarkalla ratkaisulla, jossa , jollei .) $T(n)=n+10n\log _{2}n$ $T(1) = 1$

Vaihtoehto 3

Yleinen lomake

Jos suoritetaan:

f(n)=\Omega \vasen(n^{{c}}\oikea)

missä

c>\log _{b}a

ja se on myös totta, että:

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

joillekin vakioille ja riittävän suurille (ns. säännöllisyysehto )

k<1

n

sitten:

T\left(n\right)=\Theta\left(f(n)\oikea)

Esimerkki

T(n)=2T\left({\frac {n}{2}}\right)+n^{2}

Vakioarvot ja funktiot:

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

f(n)=\Omega \vasen(n^{c}\oikea)

, missä

c = 2

Tarkistamme, että vaihtoehdon 3 suhde täyttyy:

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

, ja siten

c>\log _{b}a

Säännöllisyysehto pätee myös :

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

, valittaessa

k = 1/2

Siksi päälauseen kolmannen version mukaan:

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

Tämä rekursiivinen relaatio T ( n ) on yhtä suuri kuin Θ ( n 2 ), joka on sama kuin f ( n ) alkuperäisessä kaavassa.

(Tämän tuloksen vahvistaa tarkka toistumisratkaisu, jossa , jollei .) $T(n)=2n^{2}-n$ $T(1) = 1$

Lausekkeet, joita ei ratkaista päälauseella

Seuraavia suhteita ei voida ratkaista päälauseella: [2]

$T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}$ a ei ole vakio, päälause vaatii vakiomäärän osatehtäviä;
$T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}$ f(n):n ja välillä on ei-polynomiriippuvuus; $n^{{\log _{b}a}}$
$T(n)=0,5T\vasen({\frac {n}{2}}\oikea)+n$ a < 1, mutta päälause vaatii vähintään yhden osatehtävän;
$T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n$ f(n) on negatiivinen;
$T(n)=T\vasen({\frac {n}{2}}\oikea)+n(2-\cos n)$ lähellä vaihtoehtoa 3, mutta säännöllisyysehto ei täyty .

Toisessa esimerkissä ja ero voidaan ilmaista muodossa . Se osoittaa, että millä tahansa vakiolla . Siksi ero ei ole polynomi ja päälause ei päde. $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$

Sovellus joihinkin algoritmeihin

Algoritmi	Toistuva suhde	Työtunnit	Merkintä
Binäärihaku	$T(n)=T\vasen({\frac {n}{2}}\oikea)+O(1)$	$O(\log n)$	Päälause, 2. vaihtoehto: , jossa [3] $c=\log _{b}a$ $a=1,b=2,c=0,k=0$
Binaaripuun läpikulku	$T(n)=2T\vasen({\frac {n}{2}}\oikea)+O(1)$	$Päällä)$	Päälause, versio 1: missä [3] $c<\log _{b}a$ $a=2,b=2,c=0$
Strassenin algoritmi	$T(n)=7T\left({\frac {n}{2}}\right)+O(n^{2})$	$O(n^{\log _{2}7})\noin O(n^{2.81})$	Päälause, versio 1: , jossa [4] $c<\log _{b}a$ $a=7,b=2,c=2$
Optimaalinen lajiteltu matriisihaku	$T(n)=2T\left({\frac {n}{2}}\right)+O(\log n)$	$Päällä)$	Akra-Bazzi - lause saamista varten $p = 1$ $g(u)=\log(u)$ $\Theta (2n-\log n)$
Yhdistä lajittelu	$T(n)=2T\vasen({\frac {n}{2}}\oikea)+O(n)$	$O(n\log n)$	Päälause, 2. vaihtoehto: , missä $c=\log _{b}a$ $a=2,b=2,c=1,k=0$

Katso myös

Akra-Bazzi menetelmä

Muistiinpanot

↑ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html Arkistoitu 22. kesäkuuta 2012 Wayback Machinessa
↑ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf (kuollut linkki)
↑ 1 2 Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf Arkistoitu 21. huhtikuuta 2017 Wayback Machinessa
↑ Päälause diskreeteille jakaa ja hallitse -toistoille . Haettu 19. elokuuta 2016. Arkistoitu alkuperäisestä 18. huhtikuuta 2016. (määrätön)

Kirjallisuus

Kormen, T., Leizerson, C., Rivest, R., Stein, C. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms. - 2. - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 . Luvut 4.3 (päälause) ja 4.4 (todistus)
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Johdatus algoritmeihin. – 2. - MIT Press ja McGraw-Hill, 2001. - ISBN 0-262-53196-8 . Kohdat 4.3 (Mestarimenetelmä) ja 4.4 (Mastarilauseen todistus), ss. 73-90. (Englanti)
Michael T. Goodrich ja Roberto Tamassia . Algoritmien suunnittelu: perusta, analyysi ja Internet-esimerkit . Wiley, 2002. ISBN 0-471-38365-1 . Päälause (mukaan lukien tähän sisältyvä versio tapauksesta 2, joka on vahvempi kuin CLRS:n versio) on sivulla pp. 268-270. (Englanti)
LUKU 5. REKURSIO JA TOISTUMISET 5.2 Päälause arkistoitu 21. huhtikuuta 2017 Wayback Machinessa , CS 21/Math 19 - Kurssimuistiinpanot arkistoitu 21. heinäkuuta 2010 Wayback Machinessa , Ken Bogart ja Cliff Math, Computer Sciencete, Discrete.