Ebben az oktatóanyagban megtudhatja, mi a főtétel és hogyan használják a megismétlődési kapcsolatok megoldására.
A mester módszer egy képlet a forma megismétlődési viszonyainak megoldására:
T (n) = aT (n / b) + f (n), ahol, n = a bemenet mérete a = a rekurziós részproblémák száma n / b = az egyes részproblémák mérete. Feltételezzük, hogy az összes részprobléma azonos méretű. f (n) = a rekurzív híváson kívül végzett munka költsége, amely magában foglalja a probléma felosztásának költségét és a megoldások összevonásának költségeit. Itt a ≧ 1 és b> 1 konstansok, és f (n) aszimptotikusan pozitív funkció.
Az aszimptotikusan pozitív függvény azt jelenti, hogy kellően nagy n érték esetén megvan f(n)> 0.
A törzstételt arra használják, hogy egyszerű és gyors módon kiszámítsák az ismétlődési relációk (osztás és meghódítás algoritmusok) időbeli összetettségét.
Mester tétel
Ha a ≧ 1és b> 1állandók és f(n)egy aszimptotikusan pozitív függvény, akkor időbonyolultsága rekurzív összefüggés adja
T (n) = aT (n / b) + f (n) ahol T (n) a következő aszimptotikus határokkal rendelkezik: 1. Ha f (n) = O (n log b a-ϵ ), akkor T (n ) = Θ (n log b a ). 2. Ha f (n) = Θ (n log b a ), akkor T (n) = Θ (n log b a * log n). 3. Ha f (n) = Ω (n log b a + ϵ ), akkor T (n) = Θ (f (n)). ϵ> 0 állandó.
A fenti feltételek mindegyike úgy értelmezhető:
- Ha az egyes problémák részproblémáinak megoldási költsége egy bizonyos tényezővel megnő, akkor a értéke
f(n)polinomiálisan kisebb lesz, mint . Így az idő bonyolultságát elnyomja az utolsó szint költsége, azaz.nlogb anlogb a - Ha az alprobléma megoldásának költsége minden szinten közel azonos, akkor a értéke
f(n)lesz . Így az idő bonyolultsága a szintek összes számának a szorosa lesz, azaz.nlogb af(n)nlogb a * log n - Ha az egyes problémák részproblémáinak megoldási költsége egy bizonyos tényezővel csökken, akkor a értéke
f(n)polinomiálisan nagyobb lesz, mint . Így az idő bonyolultságát elnyomja a költség .nlogb af(n)
Megoldott példa a fő tételre
T (n) = 3T (n / 2) + n2 Itt a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 azaz. f (n) <n log b a + ϵ , ahol, ϵ állandó. A 3. eset ide utal. Így T (n) = f (n) = Θ (n 2 )
Fő tétel korlátai
A törzstétel nem használható, ha:
- A T (n) nem monoton. például.
T(n) = sin n f(n)nem polinom. például.f(n) = 2n- az a nem állandó. például.
a = 2n a < 1
