O notacija

Zapis Big O je način primerjave algoritmov. Primerja jih tako, da izračuna, koliko pomnilnika potrebujejo in koliko časa potrebujejo za dokončanje.

Zapis Veliki O se pogosto uporablja pri določanju kompleksnosti problema, znanega tudi kot razred kompleksnosti problema. Matematik Paul Bachmann (1837-1920) je prvi uporabil ta zapis v drugi izdaji svoje knjige "Analytische Zahlentheorie" leta 1896. Edmund Landau (1877-1938) je zapis populariziral. Zato se ljudje, ko govorijo o Landaujevih simbolih, sklicujejo na ta zapis.

Zapis Big O je poimenovan po izrazu "red funkcije", ki se nanaša na rast funkcij. Zapis velikega O se uporablja za iskanje zgornje meje (najvišje možne vrednosti) stopnje rasti funkcije, kar pomeni, da ugotovi najdaljši čas, ki bo potreben za pretvorbo vhoda v izhod. To pomeni, da lahko algoritem razvrstimo v skupine glede na to, koliko časa lahko traja v najslabšem primeru, ko bo vsakič izbrana najdaljša pot.

Big O je izraz, ki ugotavlja čas izvajanja po najslabšem možnem scenariju in prikazuje, kako učinkovit je algoritem, ne da bi bilo treba program zagnati na računalniku. To je uporabno tudi zato, ker imajo lahko različni računalniki različno strojno opremo in zato za izvedbo potrebujejo različno količino časa. Ker Big O vedno predpostavlja najslabši možni scenarij, lahko pokaže dosledno merjenje hitrosti: ne glede na strojno opremo bo O ( 1 ) {\displaystyle O(1)} $O(1)$ vedno končan hitreje kot O ( n ! ) {\displaystyle O(n!)}, $O(n!)$ ker imata različne stopnje učinkovitosti.

Primeri

V vseh naslednjih primerih je uporabljena koda, napisana v Pythonu. Upoštevajte, da to ni popoln seznam tipov Big O.

Stalno

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Vedno traja enako dolgo ne glede na vhodne podatke. Vzemimo na primer funkcijo, ki sprejme celo število (imenovano x) in vrne dvojno vrednost:

def double(x): return x * 2 #Vrni vrednost x krat 2

Po sprejetju vhodnega podatka bo ta funkcija vedno naredila en korak in vrnila izhodni podatek. Je konstantna, ker bo vedno potrebovala enako količino časa, torej je O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Linearno

O ( n ) {\displaystyle O(n)} $O(n)$ . Poveča se glede na velikost vhoda, ki ga predstavlja n {\displaystyle n} . Predpostavimo, da funkcija sprejme n in vrne vsa števila od 1 do n:

def count(n): i = 1 #Izdelaj števec "i" z vrednostjo 1 while i <= n: #Ker je i manjši ali enak n print(i) #Prikaz vrednosti i = i + 1 #Predefiniraj i kot "vrednost i + 1"

Če bi vnesli vrednost 5, bi se izpisalo 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} $1,2,3,4,5$ za dokončanje je potrebnih 5 zank. Podobno, če bi vnesli vrednost 100, bi se izpisalo 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ , kar bi zahtevalo 100 zank. Če je vhodnih podatkov n {\displaystyle n}, potem je čas izvajanja algoritma vsakič natanko n {\displaystyle n} zank, torej je O ( n ) {\displaystyle O(n)} $O(n)$ .

Faktorialni

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Povečuje se v faktorskih količinah, kar pomeni, da se potreben čas močno povečuje z vnosom. Recimo, da želimo obiskati pet mest po svetu in si ogledati vse možne razvrstitve (permutacije). Algoritem, ki ga lahko napišemo z uporabo Pythonove knjižnice itertools, je naslednji:

uvoz itertools #Uvoz knjižnice itertools cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #Mrežo naših izbranih mest def permutations(cities): #Za vhodno polje mest: for i in itertools. permutations(cities): #Za vsako permutacijo naših elementov (pripisano spremenljivki "i") print(i) #Izhod i

Ta algoritem bo izračunal vsako edinstveno permutacijo naših mest in jo nato prikazal. Primeri rezultatov bodo vključevali:

("London", "Pariz", "Berlin", "Amsterdam", "Rim") ("London", "Pariz", "Berlin", "Rim", "Amsterdam") ("London", "Pariz", "Amsterdam", "Berlin", "Rim") ... ("Rim", "Amsterdam", "Pariz", "Berlin", "London") ("Rim", "Amsterdam", "Berlin", "London", "Pariz") ("Rim", "Amsterdam", "Berlin", "Pariz", "London")

Tu je naš seznam vnosov dolg 5 elementov in za vsako izbiro se naše preostale možnosti zmanjšajo za 1. Z drugimi besedami, naših 5 vnosov izbere 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elementov (ali 5 ! {\displaystyle 5!} $5!$ ). Če je naš vhod dolg n {\displaystyle n} mest, potem je število izhodov n ! {\displaystyle n! } $n!$ ; z drugimi besedami, ob predpostavki, da gremo skozi vse permutacije, bomo za dokončanje potrebovali O ( n ! ) {\displaystyle O(n!)} $O(n!)$ zank.

Zapis Little-o

Strožja različica Velikega O je little-o. Razlika med velikim O in little-o je v tem, da je little-o stroga zgornja meja: medtem ko O ( n ) {\displaystyle O(n)} $O(n)$ pomeni, da se bo čas dokončanja glede na velikost vhoda povečal na to največjo vrednost, pa o ( n ) {\displaystyle o(n)} $o(n)$ pomeni, da bo čas dokončanja na splošno pod to vrednostjo. Z drugimi besedami, Big O predvideva, da bo vsaka zanka ubrala najdaljšo pot in da bo proces trajal čim dlje, medtem ko je little-o bolj realističen glede dejanskega časa izvajanja; če število zank temelji na metanju šeststranske kocke, Big O vedno predvideva, da je padla številka 6, medtem ko little-o upošteva enako verjetnost padca drugih števil.

Vprašanja in odgovori

V: Kaj je zapis Big O?

O: Zapis Big O je način primerjave hitrosti rasti različnih funkcij, ki se pogosto uporablja za primerjavo učinkovitosti različnih algoritmov z izračunom, koliko pomnilnika in časa je potrebnega za dokončanje. Uporablja se lahko tudi za ugotavljanje, kako zapleten je problem.

V: Kdo je prvi uporabil ta zapis?

O: Matematik Paul Bachmann (1837-1920) je prvi uporabil ta zapis v svoji knjigi "Analytische Zahlentheorie" leta 1896.

V: Kaj pomeni Big O?

O: Big O pomeni "red funkcije", ki se nanaša na stopnjo rasti funkcij.

V: Kako se uporablja Big O?

O: Zapis Big O se uporablja za iskanje zgornje meje (najvišje možne vrednosti) za stopnjo rasti funkcije, kar pomeni, da se določi najdaljši čas, ki bo potreben za pretvorbo vhoda v izhod. To pomeni, da lahko algoritme razvrstimo v skupine glede na to, koliko časa potrebujejo v najslabšem možnem primeru, pri čemer bo vsakič izbrana najdaljša pot.

V: Kaj so Landauovi simboli?

O: Simboli Landau se nanašajo na zapis Big O, poimenovan po Edmundu Landauu (1877-1938), ki je populariziral ta zapis.

V: Zakaj je Big O uporaben?

O:Big O nam omogoča merjenje hitrosti, ne da bi nam bilo treba izvajati programe na računalnikih, saj vedno predvideva najslabše možne scenarije, zaradi česar je konsistenten ne glede na razlike v strojni opremi med računalniki. Pokaže tudi, kako učinkovit je algoritem, ne da bi ga bilo treba dejansko zagnati na računalniku.