Tässä opetusohjelmassa opit, mikä päälause on ja miten sitä käytetään toistosuhteiden ratkaisemiseen.
Master-menetelmä on kaava lomakkeen toistosuhteiden ratkaisemiseksi:
T (n) = aT (n / b) + f (n), missä, n = syötteen koko a = rekursiossa olevien aliongelmien lukumäärä n / b = kunkin alaongelman koko. Kaikilla alaongelmilla oletetaan olevan sama koko. f (n) = rekursiivisen puhelun ulkopuolella tehdyn työn hinta, joka sisältää ongelman jakamiskustannukset ja ratkaisujen yhdistämisen kustannukset. Tässä a ≧ 1 ja b> 1 ovat vakioita ja f (n) on asymptoottisesti positiivinen toiminto.
Asymptoottisesti positiivinen funktio tarkoittaa, että meillä on riittävän suuri n-arvo f(n)> 0.
Pääteemaa käytetään laskemaan toistumissuhteiden (jako- ja valloitusalgoritmit) aikakompleksisuus yksinkertaisella ja nopealla tavalla.
Päälause
Jos a ≧ 1ja b> 1ovat vakioita ja f(n)on asymptoottisesti positiivinen funktio, niin rekursiivisen suhteen aikakompleksisuuden antaa
T (n) = aT (n / b) + f (n) missä, T (n): llä on seuraavat asymptoottiset rajat: 1. Jos f (n) = O (n log b a-ϵ ), niin T (n) ) = Θ (n log b a ). 2. Jos f (n) = Θ (n log b a ), niin T (n) = Θ (n log b a * log n). 3. Jos f (n) = Ω (n log b a + ϵ ), niin T (n) = Θ (f (n)). ϵ> 0 on vakio.
Jokainen yllä olevista ehdoista voidaan tulkita seuraavasti:
- Jos kullakin tasolla alaongelmien ratkaisemisesta aiheutuvat kustannukset kasvavat tietyllä tekijällä, arvon arvo
f(n)muuttuu polynomisesti pienemmäksi kuin . Siten ajan monimutkaisuutta tukahduttavat viimeisen tason kustannukset eli.nlogb anlogb a - Jos alaongelman ratkaisemisen kustannukset kullakin tasolla ovat lähes samat, niin arvon arvo
f(n)on . Siten ajan monimutkaisuus tulee olemaan kertaa tasojen kokonaismäärä eli.nlogb af(n)nlogb a * log n - Jos alakohteiden ratkaisemisen kustannukset kullakin tasolla laskevat tietyllä tekijällä, arvosta
f(n)tulee polynomisesti suurempi kuin . Siten ajan monimutkaisuus tukahduttaa kustannukset .nlogb af(n)
Ratkaistu esimerkki pääteorasta
T (n) = 3T (n / 2) + n2 Tässä a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ts. f (n) <n log b a + ϵ , missä, ϵ on vakio. Tapaus 3 tarkoittaa tässä. Siten T (n) = f (n) = Θ (n 2 )
Päälauseon rajoitukset
Pääteemaa ei voida käyttää, jos:
- T (n) ei ole yksitoikkoinen. esim.
T(n) = sin n f(n)ei ole polynomi. esim.f(n) = 2n- a ei ole vakio. esim.
a = 2n a < 1
