Programozási módszertan Függvények rekurzív megadása "Oszd meg és uralkodj" elv, helyettesít˝o módszer, rekurziós fa módszer, mester módszer ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
PM-03 – p. 1/13
´ Bevezetes Algoritmusok futási idejének számítása gyakran vezet rekurzív egyenlethez, különösen akkor, ha az algoritmus rekurzív. Példa: összefésülo˝ rendezés OSSZEFESULO-RENDEZES(A,bal,jobb); begin if bal<jobb then begin kozep:=(bal+jobb) div 2; OSSZEFESULO-RENDEZES(A,bal,kozep); OSSZEFESULO-RENDEZES(A,kozep,jobb); OSSZEFESUL(A,bal,kozep,jobb); end end;
PM-03 – p. 2/13
´ uralkodj elvu˝ algoritmusok Oszd meg es • T (n) futási ido˝ az n méretu˝ bemenetre • Tegyük fel, hogy az algoritmus a kimenetet közvetlenül
kiszámítja, ha n < c valamilyen c konstansra • A bemenetet a db részre osztja, amelyek mérete
n b
és
ezeket a feladatokat rekurzívan oldja meg • D(n) ido˝ kell a részekre osztáshoz, C(n) ido˝ a
részproblémák megoldásaiból összerakni a kiindulási feladat megoldását • futási ido: ˝
T (n) =
(
Θ(1), ha n ≤ c, ´ ent ´ aT ( nb ) + D(n) + C(n), egyebk
PM-03 – p. 3/13
¨ ´ ul ´ eseten ´ Osszef es ¨ o˝ rendezes a = 2 D(n) = Θ(1) ˝ az összefésülés elvégezheto˝ lineáris idoben: C(n) = Θ(n) ˝ futási ido: ( Θ(1), ha n = 1, T (n) = 2T ( n2 ) + Θ(n), ha n > 1
Az egyenlet átírása után: ( T (n) =
c, ha n = 1, 2T ( n2 ) + c(n), ha n > 1
Felrajzolható a rekurziós fa
⇒ T (n) = Θ(nlgn)
PM-03 – p. 4/13
Rekurziós fa
PM-03 – p. 5/13
´ fa modszer ´ Rekurzios 1 A rekurziós fa olyan fa, amelynek minden pontja egy eljáráshívást jelent adott aktuális paraméterekre, úgy, hogy a pont fiai megfelelnek azoknak az eljáráshívásoknak, amelyek végrehajtódnak az aktuális paraméterek esetén.
Szintenként összegezzük a pontok költségét, majd a szinteket összeadva kapjuk a teljes költséget. Mivel a részproblémák mérete egyre csökken, ahogy egyre ˝ elobb-utóbb ˝ távolabb kerülünk a gyökértol, a részprobléma mérete olyan kicsi lesz, hogy rá nem a rekurziós képlet vonatkozik, hanem a kezdeti feltétel. ˝ Milyen messze leszünk ekkor a gyökértol?
PM-03 – p. 6/13
´ fa modszer ´ Rekurzios 2 Példa: Oldjuk meg a T (n) = 3T (⌊ n4 ⌋)+Θ(n2 ) rekurzív egyenletet.
• az i-edik szinten lévo˝ részprobléma mérete n/4i • a részprobléma mérete akkor lesz 1, ha n 4i
= 1 ⇒ i = log4 n ⇓
a fának log4 n + 1 szintje van (0, 1, 2, . . . log4 n)
PM-03 – p. 7/13
´ fa modszer ´ Rekurzios 3 • Ezután meghatározzuk a fa minden szintjének költségét. • Minden szinten 3-szor annyi pont van, mint a felette lévo˝
szinten ⇒ az i-dik szinten 3i pont van. • A részproblémák mérete szintenként negyedére csökken,
ezért minden szinten i = 0, 1, 2, . . . , log4 n − 1 -re a költség c( 4ni )2 • Ezeket összegezve az összes pontra azt kapjuk, hogy az
i-edik szinten lévo˝ pontok költsége 3 i 2 i = 0, 1, 2, . . . , log4 n − 1 -re 3i c( 4ni )2 = ( 16 ) cn • Az utolsó log4 n-edik szinten 3log4 n = nlog4 3 pont van,
mindegyik T(1) költségu˝ ⇒ nlog4 3 T (1) az utolsó szint költsége, ami Θ(nlog4 3 )
PM-03 – p. 8/13
´ fa modszer ´ Rekurzios 4 A teljes fára összegezve: 3 2 2 3 log4 n−1 2 3 cn2 + ( 16 ) cn + . . . + ( 16 ) cn + Θ(nlog4 3 ) T (n) = cn2 + 16 Plog4 n−1 3 i 2 = i=0 ( 16 ) cn + Θ(nlog4 3 ) P∞ 3 i 2 < i=0 ( 16 ) cn + Θ(nlog4 3 ) = 1−(1 3 ) cn2 + Θ(nlog4 3 ) 16
= O(n2 )
PM-03 – p. 9/13
´ Helyettes´ıto˝ modszer Lépések: 1. Sejtsük meg a megoldást. 2. Teljes indukcióval határozzuk meg a konstansokat és igazoljuk a megoldás helyességét.
PM-03 – p. 10/13
´ Helyettes´ıto˝ modszer Példa: Határozzuk meg a T (n) = 2T (⌊ n2 ⌋) + n egyenlet egy felso˝ korlátját! Sejtésünk az, hogy T (n) = O(n lg n). Megmutatjuk, hogy alkalmas c > 0 konstansra T (n) ≤ cn lg n. Tegyük fel, hogy ⌊ n2 ⌋-re teljesül a bizonyítandó, azaz n n n T (⌊ ⌋) ≤ c⌊ ⌋ lg(⌊ ⌋) 2 2 2
Ezt behelyettesítve a rekurzív egyenletbe kapjuk, hogy T (n) ≤ 2(c⌊ n2 ⌋ lg(⌊ n2 ⌋)) + n ≤ cn lg( n2 ) + n = cn lg n − cn lg 2 + n = cn lg n − cn + n ≤ cn lg n, ha c ≥ 1
PM-03 – p. 11/13
A mester módszer
PM-03 – p. 12/13
´ Mester tetel A T (n) = aT ( nb ) + f (n) típusú rekurzív egyenletek megoldására ad receptet, ahol a ≥ 1 és b > 1 konstansok, valamint f (n) aszimptotikusan pozitív függvény. Tétel: Legyenek a ≥ 1 és b > 1 konstansok, f (n) függvény, T (n) pedig a nemnegatív egészeken a T (n) = aT ( nb ) + f (n) rekurzív egyenlettel definiált függvény, ahol nb jelentheti akár az ⌊ nb ⌋, akár az ⌈ nb ⌉ értéket. Ekkor T (n)-re a következo˝ aszimptotikus korlátok adhatók. 1. Ha f (n) = O(nlogb a−ε ) valamely ε > 0 konstansra, akkor T (n) = Θ(nlogb a ) 2. Ha f (n) = Θ(nlogb a ), akkor T (n) = Θ(nlogb a lg n) 3. Ha f (n) = Ω(nlogb a+ε ) valamely ε > 0 konstansra, és ha af ( nb ) ≤ cf (n) valamely c < 1 konstansra és eléggé nagy n-re, akkor T (n) = Θ(f (n)) PM-03 – p. 13/13
