Chapter 3. Függvények növekedési rendje

A későbbi fejezetekben, bonyolultságelméleti vizsgálatoknál, szükségünk lesz arra, hogy függvények növekedési rendjét (aszimptotikus, azaz a végtelenhez tartó viselkedését) egységes formában ki tudjuk fejezni. Ehhez lényegében egy olyan formulát fogunk használni, amelyik segítségével egy függvényből egyszerűen le tudjuk választani a legfontosabb, legmeredekebben növő összetevőjét.

3.1. Definíció

Legyen  egy monoton növekvő függvény. Az 
 halmazt az 
             függvény növekedési 
rendjébe tartozó függvények osztályának nevezzük.
Ha  , azt mondjuk, hogy "   egy nagy ordó  " függvény.

3.2. Megjegyzés

A növekedési rend egyértelművé tételéhez a legtisztább, ha 
 -ről feltesszük, hogy monoton növekvő, de ez nem feltétlenül 
szükséges. Ez a feltételezés sok vizsgálatot feleslegesen 
elbonyolítana, az érthetőséget rontaná. 

A  helyett gyakran a hagyományos  jelölést használják.

A definíció alapján legnyilvánvalóbb példa, ha egy függvény felülről korlátoz egy másikat. Erre azonban nem feltétlenül van szükség. Az alábbiakban néhány szemléletes példán keresztül megvizsgáljuk, hogy első megközelítésben mit is fejez ki a növekedési rend.

Example 3.1. 1. példa

Ha feltételezzük, hogy , akkor a definíció feltételei , választással teljesülnek.

Figure 3.1. 1. ábra

1. ábra



Example 3.2. 2. példa

Ha feltételezzük, hogy , ha , kis-ek esetén nem törődünk a függvények viszonyával.

Figure 3.2. 2. ábra

2. ábra



Example 3.3. 3. példa

Itt , viszont egy konstanssal megszorozva már nem kisebb mint .

Figure 3.3. 3. ábra

3. ábra



3.3. Tulajdonságok

1.  (reflexivitás)
2.  minden  esetén 
3. Legyen  és . Ekkor  (tranzitivitás)

Bizonyítás

1. Legyen és . Mivel minden esetén, így minden esetén.

2. Legyen és . Ekkor , azaz , minden esetén. ✓

3. Legyen és olyan, hogy , ha és és olyan, hogy , ha . Ekkor és választással azt kapjuk, hogy , ha és , azaz .

3.4. Megjegyzés

1. A tranzitív tulajdonság kifejezi azt az elvárásunkat, hogy egy  
függvény gyorsabban nő, mint  , akkor minden olyan függvénytől is 
gyorsabban nő, amelyiktől  gyorsabb. 

2. A növekedési rend definíciója alapján nem csak monoton függvényekre 
értelmezhető, de abban az esetben a vizsgálataink szempontjából nem 
értékes a jelentése. 

3. A növekedési rendekre sem a szimmetria, sem az antiszimmetria nem 
teljesül. A szimmetriára ( ) az  és  
függvénypár, míg az antiszimmetriára ( )
az  és  függvénypár jelent ellenpéldát. 

3.5. További tulajdonságok

4. Legyen  és . Ekkor  .
5. Legyen  és . Ekkor .
6. Legyen  monoton növekvő, amire  
          és . 
Ekkor .

Bizonyítás

3. Tegyük fel, hogy és -re illetve , -re teljesül, hogy és . Legyen és . Ekkor .

4. Hasonlóan az előzőhöz, tegyük fel, hogy és -re illetve , -re teljesül, hogy és . Legyen és . Ekkor .

5. Tegyük fel, hogy -re illetve -re teljesül, hogy . Az általánosság megszorítása nélkül feltehetjük, hogy . Mivel a függvény szigorúan monoton növekvő, ezért . Mivel , ezért .

Legyen . monotonitása miatt , és

3.6. Következmények

1. Legyen ! Ekkor  akkor és csak akkor, ha . 
2. Legyen ! Ekkor  akkor és csak akkor, ha . 
3. Legyen k > 0! Ekkor  és . 
4. Legyen ! Ekkor .

Bizonyítás

Az 1., 2., 3. és 4. következmények egyszerű megfontolással származtathatók az 4.,5. és 6. tulajdonságokból.

A következőkben definiálunk egy érdekes függvénysorozatot illetve hozzájuk kapcsolódóan egy rendkívül gyorsan növő függvényt.

3.7. Definíció

Legyen ,  egy függvénysorozat, melyekre teljesülnek 
a következő tulajdonságok:
1. 
2. 
3. 
      

A függvénysorozat első néhány eleme a jól ismert aritmetikai műveleteket adja vissza.

  1. a rákövetkező,

  2. az összeadás, azaz

  3. a szorzás, azaz

  4. a hatványozás, azaz

művelete.

A definíció lényegében a szokásos meghatározásoknak a kiterjesztése:

  1. az összeadás értelmezése, hogy -et -szor növeljük -el;

  2. a szorzás értelmezése, hogy -et -szor adjuk össze önmagával;

  3. a hatványozásnál -et -szor szorozzuk össze önmagával; stb.

Ilyen módon egyre gyorsabban növő függvényeket kapunk. A függvénysorozatot felhasználva tudunk készíteni egy olyan függvényt, amelyik a sorozat minden elemétől jobban nő: . Szokás közvetlenül, a függvénysorozat felhasználása nélkül is definiálni egy ehhez kapcsolódó, rendkívül gyorsan növő függvényt.

3.9. Definíció

Ackermann-függvény: 
Legyen  függvény adott a következő rekurzív 
definícióval:
1. 
2. 
3. 
Az  függvényt Ackermann-függvénynek nevezzük.

Az nagyjából az -nek megfelelő értéket vesz fel (valamivel kisebb). első néhány függvényértéke:

, ahol k egy több mint jegyű szám.

Világos, hogy ez az érték messze meghaladja a az elképzelhető, vagy akár a lejegyezhető értéket. (Jóval nagyobb, mint a világegyetem összes atomjának száma.) És a növekedése egyre nagyobb ütemű.

A növekedési rendek pontosabb kifejezésére más definíciókat is szokás használni. Ezek közül néhány fontosabbat megadunk a következő oldalakon, megvizsgálva egy-két alapvető tulajdonságukat.

3.10. Definíció

Legyen   egy függvény. 
A 
halmazt az  függvény pontos növekedési rendjébe tartozó függvények 
osztályának nevezzük.

3.11. Tulajdonságok

1. Legyen  két függvény. Ekkor  akkor és csak akkor, 
   ha .
2. Legyen  két függvény. Ekkor  akkor és csak akkor, 
   ha  és 
         

Bizonyítás

1. Legyen és olyan , hogy , ha , valamint és . Ekkor az első egyenlőtlenség alapján , ha illetve a második egyenlőtlenség alapján , ha . Ezzel tulajdonképpen az állítást igazoltuk.

2. A és relációk definíciója alapján és valamint és , amelyekre , ha és , ha . Legyen és . Az előző két egyenlőtlenség alapján azt kapjuk, hogy , ha . ✓

3.12. Definíció

Legyen   egy függvény. Az  
halmazt az  függvénytől kisebb növekedési rendű függvények 
osztályának nevezzük.
Ha , azt mondjuk, hogy " egy kis ordó " függvény.

3.14. Tulajdonságok

1. Legyen  két függvény. Ekkor  akkor és 
csak akkor,    ha . 
2. Legyen  egy függvény. Ekkor . 
3. Legyen  egy függvény. Ekkor . 

Bizonyítás

1. Legyen és olyan , hogy , ha . Ekkor , ha , azaz akármilyen kis esetén megadható egy korlát, hogy az -től nagyobb -ek esetén . Ez a határérték definíciója alapján pontosan azt jelenti, hogy . Visszafelé, azt jelenti, hogy esetén , amelyikre , ha . Ez alapján -nel beszorozva pontosan a keresett állítást kapjuk.

2. A definíciók alapján világos, hogy és . Legyen . A definíciók alapján ekkor és , amelyekre , ha , és esetén úgy, hogy ha . Legyen . Erre az -re igaz, hogy ha , ami pontosan a bizonyítandó állítás.

3. Indirekt módon, ha feltételezzük, hogy , akkor . Erre a -re igaz, hogy és , amelyekre ha , továbbá , úgy, hogy , ha . Legyen . Erre az -re igaz, hogy és , ha , ami ellentmondás. ✓