Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

1.9. A növekedési rend fogalma, az ordo szimbolika

1.9. A növekedési rend fogalma, az ordo szimbolika

Egy algoritmus időbonyolultsága (vagy akár a tárkapacitás bonyolultsága) az input méretének monoton növekvő függvénye. Az ilyen függvényeket növekedést leíró függvényeknek (röviden növekedési függvény) nevezzük.

1.20. Példa. A kézi négyzetgyökvonás algoritmusa esetén ha az input az (egész szám), akkor az input mérete . A négyzetgyököt csak egész jegy pontosságig határozzuk meg. Ebben az esetben számú számjegyet kell meghatározni. Minden új számjegy esetén eggyel nő a visszaszorzandó szám jegyeinek a száma, tehát lineárisan nő minden lépésben a műveleti idő. A műveleti idők összege ezáltal időegység, ahol az egy számjegyre eső műveleti idő. Az input méretével ez kifejezve: . Láthatóan ez az -től függő függvény monoton növekvő.

Az egyes függvények növekedését a növekedés rendjével jellemezzük, amely valamely előre rögzített függvényhez (etalonhoz) történő hasonlítást jelent. A hasonlítást az alábbi úgynevezett ordo szimbolika által előírt módon végezzük el. Legyen két növekedést leíró függvény.

1.20. Definíció. Az ordo szimbolika szimbólumai

Azt mondjuk, hogy az függvény növekedési rendje:

Az és a többi jelölés tulajdonképpen nem szerencsés, mert azt sugalmazza, mintha itt két függvény, az és a , valamilyen közelségéről, egyezőségéről lenne szó. Valójában az egyenlőségjel jobboldalán nem egy függvény, hanem egy általa leírt függvényosztály, függvények egy halmaza áll. A baloldalon álló egyetlen függvény nem lesz egyenlő egy halmazzal. Szerencsésebb lenne az egyenlőségjel helyett a halmaz eleme jelet használni, jelezve, hogy az függvény olyan tulajdonságú, mint a által definiált függvények. Tradicionális okok miatt azonban megmaradunk az egyenlőségjel használata mellett.

A gyakorlatban gyakran előforduló fontos jellemző növekedések

1.21. Definíció. A polinomiálisan gyorsabb növekedés

Azt mondjuk, hogy az növekedési függvény polinomiálisan gyorsabban nő, mint az polinom , ha létezik olyan valós szám, hogy .

1.22. Definíció. A polinomiálisan lassabb növekedés

Azt mondjuk, hogy az növekedési függvény polinomiálisan lassabban nő, mint az polinom , ha létezik olyan valós szám, hogy .

1.21. Példa. Az előbb tárgyalt függvény kvadratikus (négyzetes) növekedésű. Ezt a következőképpen láthatjuk be. Igaz az, hogy . Ezáltal fennáll a következő egyenlőtlenség

A feladatunk olyan pozitív konstansokat és pozitív probléma küszöbméretet mutatni, melyekre esetén

fennáll. Először a baloldalra keressük meg a megfelelő konstansokat. Kis átalakítás után az alábbi egyenlőtlenséget kapjuk:

Feltételezve, hogy , leoszthatunk vele. A kapott egyenlőtlenséget -re megoldva:

Pozitív értéket itt akkor kapunk, ha . Kényelmes választás lehet a . Ekkor 1.1-ből az adódik. A jobboldalra az algebrai átalakítások után az adódó egyenlőtlenség:

Pozitív problémaméret küszöböt akkor remélhetünk, ha az együtthatójára fennáll, hogy , azaz . Válasszuk a értéket. Az 1.1-ben szereplő másodfokú kifejezés alakja ekkor:

Ennek pozitív gyöke:

Tehát ebben az esetben az választás megfelelő. A két oldal elemzését összevetve a keresett megfelelő konstansok lehetnek: , , . Ez alapján teljesül az, hogy ha a probléma mérete legalább 8, akkor . Tehát valóban az algoritmusunk időigénye .

1.22. Példa. Bizonyítsuk be, hogy !

Bizonyítás: Ha az állítás igaz, akkor léteznie kell két pozitív konstansnak, melyekre valamely pozitív -tól kezdve igaz, hogy . Itt -nel leosztva és egyenlőtlenségek adódnak. Látszik, hogy kell legyen. Válasszuk értéket. Ebben az esetben miatt adódik. Tehát lehet például 3. A másik egyenlőtlenségből pedig mivel mindig kisebb, mint 3, ezért lehet 3, vagy annál nagyobb szám, pedig lehet tetszőleges. Összegezve: , , és megfelelő választás, azaz ha , akkor .

1.23. Példa. Bizonyítsuk be, hogy !

Bizonyítás: A definícó értelmében legyen tetszőleges pozitív konstans. Keressünk hozzá pozitív -at, amelytől kezdve fennáll. Itt -nel leosztva adódik. Átrendezéssel , amiből az megfelelő választás a definíció kielégítésére, azaz, ha , akkor a -nél nagyobb problémaméretek esetén .

1.24. Példa. bármely esetén, azaz a logaritmus függvény lassabban nő, mint bármely pozitív kitevőjű hatványfüggvény. Ennek belátására meg kell mutatnunk, hogy bármely pozitív konstans esetén valamely küszöbtől kezdve . Ez minden bizonnyal fennáll, ha belátjuk, hogy . Ekkor ugyanis a limesz definíciójának megfelelően a hányadosnak valamely küszöbtől kezdve alá kell csökkenni akármilyen kicsi pozitív szám is ez a . Természetesen az küszöb -től függ. A határérték kiszámításához az -et először helyettesítjük a valós -szel és arra számítjuk a limeszt. A típusa , így az analízisből ismert L'Hospital szabályt alkalmazva . Az is látható innen, hogy nemcsak lassabban nő, mint , hanem polinomiálisan lassabban nő, hiszen esetén -tól is lassabban nő.