Ebben az oktatóanyagban megtudhatja, mi az aszimptotikus jelölés. Ezenkívül megismerheti a Big-O jelölést, a Theta jelölést és az Omega jelölést.
Az algoritmus hatékonysága az algoritmus végrehajtásához szükséges idő, tárhely és egyéb erőforrások nagyságától függ. A hatékonyságot aszimptotikus jelölések segítségével mérik.
Előfordulhat, hogy egy algoritmus nem azonos teljesítményű a különböző típusú bemeneteknél. A bemeneti méret növekedésével a teljesítmény megváltozik.
Az algoritmus teljesítményének változásának tanulmányozása a bemeneti méret sorrendjének változásával aszimptotikus elemzésként van meghatározva.
Aszimptotikus jelölések
Aszimptotikus jelölések azok a matematikai jelölések, amelyeket egy algoritmus futási idejének leírására használnak, amikor a bemenet egy adott érték vagy egy korlátozó érték felé halad.
Például: Buborékos rendezésnél, amikor a bemeneti tömb már rendezve van, az algoritmus által elvárt idő lineáris, azaz a legjobb eset.
De ha a bemeneti tömb fordított állapotban van, akkor az algoritmus az elemek rendezéséhez, azaz a legrosszabb esethez a maximális idő (kvadratikus) szükséges.
Ha a bemeneti tömb nincs rendezve és nem fordított sorrendben, akkor átlagos időbe telik. Ezeket az időtartamokat aszimptotikus jelölésekkel jelöljük.
Főleg három aszimptotikus jelölés létezik:
- Big-O jelölés
- Omega jelölés
- Theta jelölés
Big-O jelölés (O-jelölés)
A Big-O jelölés egy algoritmus futási idejének felső határát jelenti. Így az algoritmus legrosszabb esetét adja.
A Big-O megadja a függvény felső határát
O (g (n)) = (f (n): léteznek pozitív konstansok c és n 0 , hogy 0 ≦ f (n) ≦ CG (n) minden n ≧ n 0 )
A fenti kifejezés leírható úgy, hogy egy függvény f(n)a halmazhoz tartozik, O(g(n))ha létezik olyan pozitív állandó c, amely elég nagy között van 0és cg(n)elég nagy n.
Az nalgoritmus futási ideje nem haladja meg a (z) értékét O(g(n)).
Mivel ez ad egy algoritmus legrosszabb futási idejét, széles körben használják algoritmus elemzésére, mivel mindig érdekel minket a legrosszabb eset.
Omega jelölés (Ω-jelölés)
Az Omega jelölés egy algoritmus futási idejének alsó határát jelenti. Így biztosítja a legjobb esetben az algoritmus komplexitását.
Az Omega megadja a függvény alsó határát
Ω (g (n)) = (f (n): léteznek pozitív konstansok c és n 0 , hogy 0 ≦ CG (n) ≦ f (n) minden n ≧ n 0 )
A fenti kifejezés leírható úgy, hogy egy függvény f(n)a halmazhoz tartozik, Ω(g(n))ha létezik olyan pozitív konstans c, amely cg(n)kellően nagy legyen fent n.
Bármely értéke nesetén az algoritmus által igényelt minimális időt az Omega adja meg Ω(g(n)).
Theta jelölés (Θ-jelölés)
A theta jelölés felülről és alulról zárja le a függvényt. Mivel ez egy algoritmus futási idejének felső és alsó határát képviseli, ezért egy algoritmus átlagos eset komplexitásának elemzésére szolgál.
A téta korlátozza a függvényt az állandó tényezőkön belül
Egy függvény g(n)esetében Θ(g(n))a reláció adja meg:
Θ (g (n)) = (f (n): léteznek olyan pozitív c 1 , c 2 és n 0 konstansok , hogy 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) n ≧ n 0 )
A fenti kifejezés leírható úgy, hogy egy függvény f(n)a halmazhoz tartozik, Θ(g(n))ha vannak pozitív állandók, és olyanok , amelyek megfelelő nagyságú n közé és elég nagy n érték közé illeszthetők .c1c2c1g(n)c2g(n)
Ha egy függvény f(n)bárhol a kettő között van és mindenki számára , akkor azt mondják, hogy aszimptotikusan szorosan kötött.c1g(n)c2g(n)n ≧ n0f(n)
