In deze tutorial leer je wat een hoofdstelling is en hoe deze wordt gebruikt voor het oplossen van herhalingsrelaties.
De mastermethode is een formule voor het oplossen van herhalingsrelaties van de vorm:
T (n) = aT (n / b) + f (n), waarbij, n = grootte van invoer a = aantal subproblemen in de recursie n / b = grootte van elk subprobleem. Aangenomen wordt dat alle subproblemen dezelfde omvang hebben. f (n) = kosten van het werk gedaan buiten de recursieve aanroep, inclusief de kosten van het verdelen van het probleem en de kosten van het samenvoegen van de oplossingen Hier zijn a ≧ 1 en b> 1 constanten, en f (n) is een asymptotisch positief functie.
Een asymptotisch positieve functie betekent dat we voor een voldoende grote waarde van n hebben f(n)> 0.
De hoofdstelling wordt gebruikt om de tijdcomplexiteit van herhalingsrelaties (verdeel en heers-algoritmen) op een eenvoudige en snelle manier te berekenen.
Master Theorema
Als a ≧ 1en b> 1constanten zijn en f(n)een asymptotisch positieve functie is, dan wordt de tijdcomplexiteit van een recursieve relatie gegeven door
T (n) = aT (n / b) + f (n) waarbij T (n) de volgende asymptotische grenzen heeft: 1. Als f (n) = O (n log b a-ϵ ), dan is T (n ) = Θ (n logboek b een ). 2. Als f (n) = Θ (n log b a ), dan is T (n) = Θ (n log b a * log n). 3. Als f (n) = Ω (n log b a + ϵ ), dan is T (n) = Θ (f (n)). ϵ> 0 is een constante.
Elk van de bovenstaande voorwaarden kan worden geïnterpreteerd als:
- Als de kosten voor het oplossen van de deelproblemen op elk niveau met een bepaalde factor toenemen, wordt de waarde van
f(n)polynoom kleiner dan . Dus de tijdcomplexiteit wordt onderdrukt door de kosten van het laatste niveau, dwz.nlogb anlogb a - Als de kosten van het oplossen van de sub-probleem op elk niveau is bijna gelijk, dan is de waarde van
f(n)zal zijn . De tijdcomplexiteit is dus maal het totale aantal niveaus, dwz.nlogb af(n)nlogb a * log n - Als de kosten voor het oplossen van de subproblemen op elk niveau met een bepaalde factor dalen, wordt de waarde van
f(n)polynoom groter dan . De tijdcomplexiteit wordt dus onderdrukt door de kosten van .nlogb af(n)
Opgelost voorbeeld van hoofdstelling
T (n) = 3T (n / 2) + n2 Hier, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 dwz. f (n) <n log b a + ϵ , waarbij ϵ een constante is. Geval 3 impliceert hier. Dus T (n) = f (n) = Θ (n 2 )
Beperkingen van de hoofdstelling
De hoofdstelling kan niet worden gebruikt als:
- T (n) is niet monotoon. bijv.
T(n) = sin n f(n)is geen polynoom. bijv.f(n) = 2n- a is geen constante. bijv.
a = 2n a < 1
