Mikä on Big-O-merkintä?

Oletko koskaan miettinyt, miksi kirjoittamasi ohjelma käynnistyi niin kauan? Ehkä haluat tietää, pystytkö tekemään koodistasi tehokkaamman. Ymmärtäminen, miten koodi toimii, voi viedä koodisi seuraavalle tasolle. Big-O-notaatio on kätevä työkalu laskemaan koodisi tehokkuus.

Mikä on Big-O-merkintä?

Big-O-merkinnät antavat sinulle tavan laskea kuinka kauan koodin suorittaminen kestää. Voit fyysisesti ajastaa kuinka kauan koodisi suorittaminen kestää, mutta tällä menetelmällä on vaikea saada kiinni pienistä aikaeroista. Esimerkiksi 20–50 koodirivin suorittamisen välinen aika on hyvin pieni. Suuressa ohjelmassa nämä tehottomuudet voivat kuitenkin lisääntyä.

Big-O-merkintä laskee, kuinka monta vaihetta algoritmin on suoritettava tehokkuuden mittaamiseksi. Koodiin lähestyminen tällä tavalla voi olla erittäin tehokasta, jos sinun on viritettävä koodisi tehokkuuden lisäämiseksi. Big-O-merkinnän avulla voit mitata erilaisia ​​algoritmeja suorittamiseen tarvittavien vaiheiden lukumäärällä ja verrata objektiivisesti algoritmien tehokkuutta.

Kuinka lasket Big-O-notaation

Tarkastellaan kahta toimintoa, jotka laskevat kuinka moni sukka on laatikossa. Jokainen toiminto ottaa sukkaparien määrän ja palauttaa yksittäisten sukkien lukumäärän. Koodi on kirjoitettu Pythonissa, mutta se ei vaikuta siihen, kuinka laskemme vaiheiden määrän.

Algoritmi 1:

def sockCounter (numeroOfPairs):
individualSocks = 0
x: lle alueella (numberOfPairs):
individualSocks = individualSocks + 2
palauta individualSocks

Algoritmi 2:

def sockCounter (numeroOfPairs):
paluunumeroOfPairs * 2

Tämä on typerä esimerkki, ja sinun pitäisi pystyä kertomaan helposti mikä algoritmi on tehokkaampi. Mutta harjoittelemme, juoksemme jokaisen läpi.

LIITTYVÄT: Mikä on toiminto ohjelmoinnissa?

Mikä on toiminto ohjelmoinnissa?

Jos opit ohjelmoimaan oman koodisi, sinun on ymmärrettävä, mitkä toiminnot ovat.

Algoritmilla 1 on monia vaiheita:

1. Se antaa nollan arvon muuttujalle individualSocks.
2. Se määrittää muuttujalle i arvon yhden.
3. Se vertaa i: n arvoa numberOfPairsiin.
4. Se lisää kaksi yksittäiseen sukkaan.
5. Se osoittaa yksilöllisten sukkien lisääntyneen arvon itselleen.
6. Se lisää i: tä yksitellen.
7. Sitten se palaa vaiheiden 3-6 läpi yhtä monta kertaa kuin (indiviualSocks - 1).

Algoritmille suoritettavien vaiheiden määrä voidaan ilmaista seuraavasti:

4n + 2

On neljä vaihetta, jotka meidän on suoritettava n kertaa. Tällöin n olisi yhtä suuri kuin numberOfPairs. On myös 2 vaihetta, jotka suoritetaan kerran.

Algoritmilla 2 on vain yksi askel. NumberOfPairs-arvo kerrotaan kahdella. Ilmaisemme sen seuraavasti:

1

Jos se ei ollut jo ilmeistä, voimme nyt helposti nähdä, että algoritmi 2 on melko vähän tehokkaampi.

Big-O-analyysi

Yleensä, kun olet kiinnostunut algoritmin Big-O-merkinnästä, olet kiinnostunut enemmän kokonaishyötysuhteesta ja vähemmän vaiheiden lukumäärän hienorakeisesta analyysistä. Merkintöjen yksinkertaistamiseksi voimme vain ilmoittaa tehokkuuden suuruuden.

Yllä olevissa esimerkeissä algoritmi 2 ilmaistaan ​​yhtenä:

O (1)

Algoritmi 1 yksinkertaistettaisiin kuitenkin seuraavasti:

Päällä)

Tämä nopea tilannekuva kertoo meille, kuinka yhden algoritmin tehokkuus on sidottu n: n arvoon. Mitä suurempi luku, sitä enemmän vaiheita algoritmin on suoritettava.

Lineaarinen koodi

Koska emme tiedä n: n arvoa, on hyödyllistä miettiä, kuinka n: n arvo vaikuttaa suoritettavan koodin määrään. Algoritmissa 1 voidaan sanoa, että suhde on lineaarinen. Jos piirrät vaiheiden määrän vs. n: n arvo saa suoran viivan, joka nousee.

Toissijainen koodi

Kaikki suhteet eivät ole yhtä yksinkertaisia ​​kuin lineaarinen esimerkki. Kuvittele, että sinulla on 2D-taulukko ja haluat etsiä arvoa taulukosta. Voit luoda seuraavan algoritmin:

def searchForValue (targetValue, arraySearched):
foundTarget = Väärä
x: lle ryhmässä
y: lle x: ssä:
jos (y == kohde-arvo):
foundTarget = Tosi
return foundTarget

Tässä esimerkissä vaiheiden määrä riippuu arraySearched -ryhmän lukumäärästä ja kunkin taulukon arvojen määrästä. Niinpä yksinkertaistettu vaiheiden lukumäärä olisi n * n tai n².

Tämä suhde on neliöllinen suhde, mikä tarkoittaa, että algoritmin vaiheiden määrä kasvaa eksponentiaalisesti n: n kanssa. Big-O-merkinnässä kirjoitat sen seuraavasti:

O (n²)

LIITTYVÄT: Hyödyllisiä työkaluja CSS-tiedostojen tarkistamiseen, puhdistamiseen ja optimointiin

Logaritminen koodi

Vaikka on olemassa monia muita suhteita, viimeinen suhde, jota tarkastelemme, on logaritmiset suhteet. Muistin päivittämiseksi numeroloki on eksponenttiarvo, jota tarvitaan tukiasemaan annetun numeron saavuttamiseksi. Esimerkiksi:

log 2 (8) = 3

Loki on yhtä suuri kuin kolme, koska jos perusta olisi 2, tarvitsisimme eksponentin arvon 3 päästäksesi numeroon 8.

Joten logaritmisen funktion suhde on päinvastainen eksponenttiselle suhteelle. Kun n kasvaa, tarvitaan vähemmän uusia vaiheita algoritmin ajamiseksi.

Ensi silmäyksellä tämä vaikuttaa intuitiiviselta. Kuinka algoritmin vaiheet voivat kasvaa hitaammin kuin n? Hyvä esimerkki tästä on binaarihaut. Tarkastellaan algoritmia luvun etsimiseen yksilöllisten arvojen joukosta.

• Aloitamme hakutaulukolla, joka on järjestyksessä pienimmästä suurimpaan.
• Seuraavaksi tarkistamme arvon keskellä taulukkoa.
• Jos numero on suurempi, jätämme pois pienemmät numerot haustamme ja jos numero oli pienempi, jätämme pois suuremmat luvut.
• Katsotaan nyt jäljellä olevien numeroiden keskimmäistä lukua.
• Jälleen suljetaan pois puolet luvuista sen perusteella, onko tavoitearvomme suurempi tai pienempi kuin keskiarvo.
• Jatkamme tätä prosessia, kunnes löydämme kohteemme tai toteamme, että sitä ei ole luettelossa.

Kuten näette, koska binaarihaut eliminoivat puolet mahdollisista arvoista joka kerralla, kun n kasvaa, vaikutus tuskin vaikuttaa siihen, kuinka monta kertaa tarkistamme taulukon. Ilmaisemme tämän Big-O-merkinnällä kirjoitamme:

O (log (n))

Big-O-merkinnän merkitys

Big-O-kansakunta antaa sinulle nopean ja helpon tavan kommunikoida algoritmin tehokkuudesta. Tämä helpottaa eri algoritmien valitsemista. Tämä voi olla erityisen hyödyllistä, jos käytät kirjaston algoritmia etkä välttämättä tiedä, miltä koodi näyttää.

Kun opit ensin koodaamaan, aloitat lineaarisilla funktioilla. Kuten yllä olevasta kaaviosta näet, se vie sinut pitkälle. Mutta kun tulet kokeneemmaksi ja alat rakentaa monimutkaisempaa koodia, tehokkuudesta alkaa tulla ongelma. Ymmärtäminen koodisi tehokkuuden kvantifioimiseksi antaa sinulle työkalut, joita tarvitset aloittaaksesi sen virittämisen tehokkuudelle ja punnitsemalla algoritmien hyvät ja huonot puolet.

10 yleisintä ohjelmointi- ja koodausvirhettä

Koodausvirheet voivat johtaa niin moniin ongelmiin. Nämä vinkit auttavat sinua välttämään ohjelmointivirheitä ja pitämään koodisi merkityksellisenä.

Kirjailijasta