Kaj je zapis Big-O?

Ste se kdaj vprašali, zakaj je program, ki ste ga napisali, trajal tako dolgo? Morda vas zanima, ali lahko svojo kodo naredite bolj učinkovito. Razumevanje, kako se zagon kode lahko pripelje na naslednjo stopnjo. Zapis Big-O je priročno orodje za izračun učinkovitosti vaše kode.

Kaj je zapis Big-O?

Zapis Big-O vam omogoča, da izračunate, kako dolgo bo trajalo zagon vaše kode. Fizično lahko določite, koliko časa bo trajala koda, vendar je s to metodo težko ujeti majhne časovne razlike. Na primer, čas, potreben med izvajanjem 20 in 50 vrstic kode, je zelo majhen. Vendar se lahko v velikem programu ta neučinkovitost poveča.

Zapis Big-O šteje, koliko korakov mora algoritem izvesti, da oceni svojo učinkovitost. Pristop k vaši kodi na ta način je lahko zelo učinkovit, če morate svojo kodo nastaviti za večjo učinkovitost. Zapis Big-O vam bo omogočil merjenje različnih algoritmov s številom korakov, potrebnih za izvajanje, in objektivno primerjavo učinkovitosti algoritmov.

Kako izračunate oznako Big-O

Upoštevajmo dve funkciji, ki štejeta, koliko posameznih nogavic je v predalu. Vsaka funkcija vzame število parov nogavic in vrne število posameznih nogavic. Koda je napisana v Pythonu, vendar to ne vpliva na to, kako bi šteli število korakov.

Algoritem 1:

def sockCounter (numberOfPairs):
individualSocks = 0
za x v območju (numberOfPairs):
individualSocks = individualSocks + 2
vrni individualSocks

Algoritem 2:

def sockCounter (numberOfPairs):
vrnitev numberOfPairs * 2

To je neumen primer, zato bi morali zlahka ugotoviti, kateri algoritem je bolj učinkovit. Za vajo pa pojdimo skozi vsako.

POVEZANE: Kaj je funkcija programiranja?

Kaj je funkcija programiranja?

Če se učite, kako programirati svojo kodo, boste morali razumeti, katere funkcije so.

Algoritem 1 ima veliko korakov:

1. Spremenljivki individualSocks dodeli vrednost nič.
2. Spremenljivki i dodeli vrednost ena.
3. Primerja vrednost i s številomPairs.
4. Doda individualno nogavico dve.
5. Povečano vrednost posameznih nogavic dodeli sebi.
6. Sešteva i za eno.
7. Nato se vrne skozi korake 3 do 6 enako številokrat kot (indiviualSocks - 1).

Število korakov, ki jih moramo opraviti za en algoritem, lahko izrazimo kot:

4n + 2

Obstajajo štirje koraki, ki jih moramo opraviti n-krat. V tem primeru bi bila n enaka vrednosti numberOfPairs. Obstajata tudi 2 koraka, ki sta izvedena enkrat.

Za primerjavo ima algoritem 2 samo en korak. Vrednost numberOfPairs se pomnoži z dvema. To bi izrazili kot:

1

Če še ni bilo očitno, lahko zdaj zlahka vidimo, da je algoritem 2 precej učinkovitejši.

Analiza Big-O

Ko vas na splošno zanima zapis Big-O algoritma, vas bolj zanima splošna učinkovitost in manj natančna analiza števila korakov. Za poenostavitev zapisa lahko samo navedemo velikost učinkovitosti.

V zgornjih primerih bi bil algoritem 2 izražen kot en:

O (1)

Toda algoritem 1 bi bil poenostavljen kot:

O (n)

Ta hitri posnetek nam pove, kako je učinkovitost algoritma ena vezana na vrednost n. Večje kot je število, več korakov bo moral opraviti algoritem.

Linearna koda

Ker ne poznamo vrednosti n, je koristneje razmisliti, kako vrednost n vpliva na količino kode, ki jo je treba zagnati. V algoritmu 1 lahko rečemo, da je razmerje linearno. Če narišete število korakov v primerjavi z vrednost n dobite ravno črto, ki gre navzgor.

Kvadratna koda

Niso vsi odnosi tako preprosti kot linearni primer. Predstavljajte si, da imate 2D matriko in bi radi iskali vrednost v matriki. Lahko ustvarite algoritem, kot je ta:

def searchForValue (targetValue, arraySearched):
foundTarget = False
za x v arraySearched:
za y v x:
če (y == targetValue):
foundTarget = True
vrnitev foundTarget

V tem primeru je število korakov odvisno od števila nizov v arraySearched in števila vrednosti v posameznem polju. Torej, poenostavljeno število korakov bi bilo n * n ali n².

To razmerje je kvadratno razmerje, kar pomeni, da število korakov v našem algoritmu eksponentno raste z n. V zapisu Big-O bi ga zapisali kot:

O (n²)

POVEZANE: Uporabna orodja za preverjanje, čiščenje in optimizacijo datotek CSS

Logaritmična koda

Čeprav obstaja veliko drugih odnosov, je zadnji odnos, ki si ga bomo ogledali, logaritemski odnosi. Če želite osvežiti svoj spomin, je dnevnik števila eksponentna vrednost, potrebna za doseganje številke, ki je osnova. Na primer:

log 2 (8) = 3

Dnevnik je enak tri, ker če bi bila naša osnova 2, bi potrebovali eksponentno vrednost 3, da pridemo do številke 8.

Torej je razmerje logaritemske funkcije v nasprotju z eksponentnim razmerjem. Ko se n povečuje, je za zagon algoritma potrebnih manj novih korakov.

Na prvi pogled se zdi to kontraintuitivno. Kako lahko koraki algoritma rastejo počasneje kot n? Dober primer tega so binarna iskanja. Razmislimo o algoritmu za iskanje števila v nizu unikatnih vrednosti.

• Začeli bomo z nizom za iskanje po vrstnem redu od najmanjšega do največjega.
• Nato bomo preverili vrednost na sredini polja.
• Če je vaše število višje, bomo pri iskanju izločili nižje številke, če pa je bilo število nižje, pa višje.
• Zdaj si bomo ogledali srednje število preostalih števil.
• Ponovno bomo izločili polovico številk glede na to, ali je naša ciljna vrednost višja ali nižja od srednje vrednosti.
• Ta postopek bomo nadaljevali, dokler ne najdemo cilja ali ugotovimo, da ga ni na seznamu.

Kot lahko vidite, ker binarna iskanja pri vsakem prehodu odstranijo polovico možnih vrednosti, ko se n poveča, učinek na to, kolikokrat preverimo matriko, komaj vpliva. Da bi to izrazili v zapisu Big-O, bi zapisali:

O (log (n))

Pomen zapisov Big-O

Big-O nation vam omogoča hiter in enostaven način sporočanja, kako učinkovit je algoritem. Tako je lažje odločati med različnimi algoritmi. To je lahko še posebej koristno, če uporabljate algoritem iz knjižnice in ne veste nujno, kako izgleda koda.

Ko se prvič naučite kodirati, začnete z linearnimi funkcijami. Kot lahko vidite iz zgornjega grafa, boste prišli zelo daleč. Ko pa postanete bolj izkušeni in začnete graditi bolj zapleteno kodo, začne učinkovitost postajati problem. Razumevanje, kako količinsko ovrednotiti učinkovitost kode, vam bo dalo orodja, ki jih potrebujete za začetek prilagajanja učinkovitosti in tehtanje prednosti in slabosti algoritmov.

10 najpogostejših napak pri programiranju in kodiranju

Napake pri kodiranju lahko povzročijo toliko težav. Ti nasveti vam bodo pomagali, da se izognete programskim napakam in ohranite smiselno kodo.

O avtorju