O notacija
O notacija (tudi notacija veliki O) se v matematiki uporablja za opisovanje limitnega obnašanja funkcije, ko argument gre proti določeni vrednosti ali neskončnosti. Ta notacija pripada večji družini notacij, ki jih imenujemo Landauova notacija, Bachmann-Landauova notacija (imenovana po Edmundu Landau (1877 – 1938) in Paulu Bachmannu (1837 - 1920)) ali asimptotska notacija.
V računalništvu se notacija O uporablja za razvrščanje algoritmov po tem kako se odzivajo na spremembe v velikosti vhoda.
Definicija
urediNaj bosta f(x) in g(x) dve funkciji, ki sta definirani nad neko podmnožico realnih števil. Lahko zapišemo :
Če in samo, če obstoja pozitivna konstanta M tako, da je za vse dovolj velike vrednosti x , je f(x) kvečjemu z M pomnožen z g(x) v absolutno vrednost. To je f(x) = O(g(x)) samo, če in samo če obstoja pozitivno realno število M in realno število x0, da velja
- .
V mnogih primerih je predpostavka, da nas zanima samo stopnja rasti ko gre x proti neskončnosti, neveljavna. Običajno zapišemo f(x) = O(g(x)). Označevanje se lahko uporabi za prikaz obnašanja funkcije f blizu nekega realnega števila (pogosto okoli a=0). Lahko zapišemo, da je
če in samo, če obstoja takšni pozitivni števili δ in M, da velja
- .
Če je g(x) neničelen za vrednosti dovolj blizu vrednosti a se lahko obe od teh definicij združita z uporabo zgornje in spodnje limite
če in samo, če je
- .
Skupina Bachmann-Landauovih notacij
uredinotacija | ime | opis | definicija: za dovolj velike ... | definicija | opombe |
---|---|---|---|---|---|
veliki omikron; veliki O; veliki Oh | je omejena zgoraj z (do konstantnega faktorja) asimptotično | za neki k | ali |
||
veliki omega | je omejen spodaj z (do konstatnega faktorja) asimptotično | za pozitivni k | od začetka 20. stoletja so dokumenti o teoriji števil so stalno bolj uporabljali to notacijo, vendar z občutkom, da je f = o(g) napačno. | ||
veliki theta | je omejen zgoraj in spodaj z asimptotično | za neki pozitivni k1, k2 |
|
||
mali omikron; mali O; mali Oh | prevladuje asimptotično | za vsak | |||
mali omega | prevladuje asimptotsko | za vsak k | |||
On the order of | je enak asimptotsko |
Bachmann–Landauova notacija uporablja nekaj mnemotehnik. Tako lahko preberemo "omikron" kot "o-mikron" in "omega" lahko preberemo kot "o-mega".
- mnemotehnika za o-micron: Čitanje o-mikron in si lahko mislimo kot "O-manjši kot" in "o-manjši kot". Ta mnemotehnika micro/manjši se nanaša na dovolj velik vhodni parameter ali parametre, raste po stopnji, ki je manjša kot glede na or .
- mnemotehnika za o-mega : Čitanje o-mega in si lahko mislimo kot "O-večji kot". Ta mnemotehnika mega/večji: se nanaša na dovolj velik vhodni parameter ali parametre, raste po stopnji, ki je večja kot glede na ali .
- mnemotehnika za zgornji znak: Ta mnemotehnika nas spominja na to, kdaj uporabimo zgornje grške črke v in : za dovolj velik vhodni parameter ali parametre, raste po stopnji, ki bi lahko bila enaka z glede na .
- mnemotehnika za spodnji znak: Ta mnemotehnika nas spominja na to, kdaj moramo uporabiti male grške črke v in : za dovolj velik vhodni parameter ali parametre, raste po stopnji, ki je neenaka z glede na .
Razen notacije O se v računalništvu uporablja še notacija z velikim teta (Θ) in velikim omega (Ω) . V računalništvu pa se zelo redko uporablja notacija z uporabo malega omega (ω).
Zunanje povezave
uredi- Notacija „veliki O“ na MaFiRa Arhivirano 2008-12-06 na Wayback Machine. (slovensko)
- Uvod v asimptotske notacije Arhivirano 2012-07-22 na Wayback Machine. (angleško)
- Landauovi simboli na MathWorld (angleško)