Päälause (esimerkkien kanssa)

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.n^{log_b a}n^{log_b 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.n^{log_b a}f(n)n^{log_b 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 .n^{log_b a}f(n)

Ratkaistu esimerkki pääteorasta

T (n) = 3T (n / 2) + n2 Tässä a = 3 n / b = n / 2 f (n) = n ² log _b a = log ₂ 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 ² )