Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.11. A rekurzív egyenletek és a mester tétel

1.11. A rekurzív egyenletek és a mester tétel

Az algoritmusok időbonyolultságának elemzésekor sok esetben nem rendelkezünk közvetlen explicit formulával, amely megadná, hogy a méret függvényében hogyan alakul az algoritmus időigénye a legrosszabb esetben. Ismeretes lehet viszont az egyes méretek időigényei közötti kapcsolat, mivel ezt általában könnyebb felírni. Ennek a kapcsolatnak az ismeretében megpróbálhatjuk meghatározni vagy a függvényt explicite, vagy legalább annak aszimptotikus viselkedését.

1.26. Definíció. Rekurzív egyenlet

Rekurzív egyenletnek nevezzük azokat a függvényegyenleteket, amelyekben a függvény az ismeretlen, a meghatározandó, és a függvényérték a függvény -től kisebb értékű argumentumának helyein felvett értékeinek függvényeként adott.

A rekurzív egyenlet a függvényértéket a korábbi (-től kisebb helyen) felvett érték(ek) függvényére vezeti vissza. Ebben az esetben remélhetjük, hogy ha ismert az első néhány értékére a értéke, akkor a nagyobb esetére a már fokozatosan kiszámítható. Ha megadjuk ezeket az első értékeket, akkor azokat kezdőfeltételeknek (vagy kezdetiérték feltételeknek) nevezzük.

1.25. Példa. Legyen , akkor a geometriai sorozat definícióját kapjuk, mint a rekurzív egyenlet speciális esetét. Ennek megoldása triviálisan látszik, hogy , ami ismeretében egyértelműen meghatározott.

1.26. Példa. Legyen , akkor a számtani sorozat (aritmetikai sorozat) definícióját kapjuk, mint a rekurzív egyenlet speciális esetét. Ennek megoldása triviálisan látszik, hogy , ami ismeretében egyértelműen meghatározott.

1.27. Példa. Legyen és , , akkor a megoldás a Fibonacci sorozat.

A rekurzív egyenletek megoldására néhány módszert mutatunk. Egyikük a visszavezetési módszer. Nem megyünk bele bonyolult elméleti fejtegetésekbe, lényegét példákon keresztül szemléltetjük.

1.28. Példa. Legyen és . A visszavezetési módszer abban áll, hogy rendre a függvényértékeket visszavezetjük a kezdőfeltételre rekurzív behelyettesítéssel. A mi esetünkben ez így néz ki:

Az ilyen időbonyolultságú algoritmus a méret egységnyi növekedésére az idő egységnyi növekedésével válaszol. A megoldás megsejthetően . Ez teljes indukcióval be is bizonyítható. Látható az is, hogy aszimptotikusan azaz az algoritmus lineáris idejű.

1.29. Példa. Legyen és . Megoldása visszavezetéssel:

Megsejthető és teljes indukcióval belátható, hogy . Ebből pedig következik, hogy aszimptotikusan , azaz az algoritmus kvadratikus idejű.

1.30. Példa. Legyen és . Megoldása visszavezetéssel:

A függvény csak az alakú -re van értelmezve, ahol . Ezekre azt írhatjuk, hogy . Bevezetve az jelölést azt kapjuk, hogy . Egy nagyon hasonló feladatot az 1.28. Példában megoldottunk és onnan a megoldás . Akkor . Figyelembe véve, hogy , a végeredmény és , azaz az algoritmus logaritmikus idejű.

1.31. Példa. Legyen a rekurzív egyenlet , a kezdőfeltétel . Megoldása visszavezetéssel:

A megoldás a kettő egész hatványainak megfelelő helyeken egybeesik az előző feladat megoldásával. A többi helyen ellentétben az előző feladattal a megoldás értelmezve van. Megsejthető, hogy a megoldás . Erre is igaz az aszimptotika, hogy .

1.32. Példa. Olyan esetet vizsgálunk, amelyben a megoldást nem tudjuk megsejteni, de az aszimptotikát igen és teljes indukcióval bizonyítunk. Legyen . Az aszimptotikus megoldás sejthetően , azaz van olyan és , hogy ha , akkor . Helyettesítsük be az aszimptotikus sejtett megoldást az egyenletbe.

Ha most -et úgy választjuk meg, hogy a zárójelben lévő kifejezés nemnegatív legyen, akkor megkapjuk az áhított egyenlőtlenséget, miáltal a bizonyítás be is fejeződik. Az feltételezésből következik. Válasszuk most mondjuk az -et, akkor . Ebben az esetben a teljesül, tehát ha , akkor mindig fennáll , ahol a helyébe a 72, vagy bármilyen tőle nagyobb szám írható. Ezzel beláttuk, hogy a megoldás növekedési rendje valóban . Meg lehet mutatni, hogy még is fennáll.

Speciális, de a gyakorlat szempontjából sok fontos esetben a rekurzív egyenletekre az alább megfogalmazott úgynevezett mester tétel ad aszimptotikus megoldást (sok esetben meg nem ad).

1.27. Tétel. A mester tétel

Legyenek konstansok, függvény.

Definiálunk egy úgynevezett tesztpolinomot.

Legyen a rekurziós összefüggésünk: . (Az helyén vagy is állhat.) Ezen feltételek esetén igazak az alábbi állítások:

[1.] Ha polinomiálisan lassabb növekedésű, mint a tesztpolinom, akkor

[2.] Ha , akkor

[3.] Ha polinomiálisan gyorsabb növekedésű, mint a tesztpolinom, és teljesül az függvényre az úgynevezett regularitási feltétel, azaz konstans és küszöbméret, hogy esetén , akkor

A tételt nem bizonyítjuk.

1.33. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Láthatóan polinomiálisan lassabban nő, mint , mert minden esetén . Teljesülnek a mester tétel 1. pontjának a feltételei, tehát a tételt alkalmazva: .

1.34. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Továbbá . Teljesülnek a mester tétel 2. pontjának a feltételei, tehát a tételt alkalmazva: .

1.35. Példa. A mester tétel alkalmazása: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Ha , akkor , azaz polinomiálisan gyorsabban nő, mint a tesztpolinom, ugyanis . A mester tétel 3. pontjának a feltételei fognak teljesülni, ha még kimutatjuk az regularitását. Ez fennáll a következők szerint . Azaz minden pozitív -re teljesül a regularitás -gyel. A tételt alkalmazva: .

1.36. Példa. A mester tétel nem alkalmazható: . A mester tétel szerintinek tűnik az eset. Legyen . A tesztpolinom . Az igaz, hogy legalább olyan gyorsan nő, mint a tesztpolinom, mert , tehát . Az viszont nem igaz, hogy polinomiálisan gyorsabban nő, mint a tesztpolinom. Azért nem igaz, mert bármilyen pozitív esetén . Emiatt a mester tétel gyanított 3. pontja nem alkalmazható. Az aszimptotikus megoldás a mester tétellel nem adható meg. (Behelyettesítéssel be lehet bizonyítani, hogy .)