A Big Omega megmondja a függvény futási idejének alsó határát, a Big O pedig a felső határt.
Gyakran különböznek egymástól, és nem tudunk garanciát vállalni a futásidejére - ez a két határ és a bemenetek között változik. De mi történik, ha ugyanazok? Ezután megadhatunk egy theta (Θ) kötést - függvényünk ebben az idõben fog futni, függetlenül attól, hogy milyen bemenetet adunk neki.
Általában mindig theta kötést akarunk adni, ha lehetséges, mert ez a legpontosabb és legszorosabb kötés. Ha nem tudunk theta kötést adni, akkor a következő legjobb dolog a lehető legszorosabb O kötés.
Vegyünk például egy olyan függvényt, amely egy tömböt keres a 0 értékre:
def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false- Mi a legjobb eset? Nos, ha az általunk megadott tömb első értéke 0, akkor állandó időre van szükség: Ω (1)
- Mi a legrosszabb eset? Ha a tömb nem tartalmaz 0-t, akkor a teljes tömböt iteráljuk: O (n)
Adtunk neki egy omega és O kötést, akkor mi van a teával? Nem adhatunk neki egyet! Az általunk megadott tömbtől függően a futási idő az állandó és a lineáris között lesz.
Változtassunk egy kicsit a kódunkon.
def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)Gondolhat a legjobb és a legrosszabb esetre ?? Nem tehetem! Nem számít, milyen tömböt adunk neki, a tömb minden értékét át kell ismételnünk. Tehát a függvény legalább N időt vesz igénybe (Ω (n)), de azt is tudjuk, hogy nem tart tovább n időnél (O (n)). Mit is jelent ez? Funkciónk pontosan n időt vesz igénybe : Θ (n).
Ha a határok zavarosak, gondolkozzon el így. 2 számunk van, x és y. Megkapjuk, hogy x <= y és hogy y <= x. Ha x kisebb vagy egyenlő y-vel, és y kisebb vagy egyenlő x-rel, akkor x-nek egyenlőnek kell lennie y-vel!
Ha ismeri a linkelt listákat, tesztelje magát, és gondolkodjon el ezen funkciók futási idejéről!
- kap
- eltávolítani
- hozzá
A dolgok még érdekesebbé válnak, ha figyelembe vesszük a kétszeresen összekapcsolt listát!
Aszimptotikus jelölés
Hogyan mérjük az algoritmusok teljesítményértékét?
Fontolja meg, hogy az idő az egyik legértékesebb erőforrásunk. A számítás során a teljesítményt a folyamat befejezéséhez szükséges idővel mérhetjük. Ha a két algoritmus által feldolgozott adatok megegyeznek, akkor dönthetünk a probléma megoldásának legjobb megvalósításáról.
Tesszük ezt egy algoritmus matematikai határainak meghatározásával. Ezek a nagy-O, a nagy-omega és a nagy-téta, vagy egy algoritmus aszimptotikus jelölései. Egy grafikonon a nagy-O lenne a leghosszabb, amelyet egy algoritmus egy adott adathalmazra vagy a „felső határra” tehetne. A nagy-omega olyan, mint a nagy-O ellentéte, az „alsó határ”. Itt éri el az algoritmus a legnagyobb sebességet bármely adathalmaz esetében. A nagy téta vagy az algoritmus pontos teljesítményértéke, vagy a keskeny felső és alsó határ közötti hasznos tartomány.
Néhány példa:
- "A szállítás az életed során meglesz." (nagy-O, felső határ)
- - Legalább egy dollárt fizethetek neked. (nagy-omega, alsó határ)
- "A magas ma 25 ° C, az alacsony pedig 19 ° C lesz." (nagy-téta, keskeny)
- - Egy kilométeres sétára van a strandtól. (nagy-theta, pontos)
Több információ:
//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/