Mikä on Big-O-merkintä?

Mikä on Big-O-merkintä?

Oletko koskaan miettinyt, miksi kirjoittamasi ohjelman suorittaminen kesti niin kauan? Ehkä haluat tietää, voitko tehdä koodistasi tehokkaamman. Koodin suorittamisen ymmärtäminen voi nostaa koodisi seuraavalle tasolle. Big-O-merkintätapa on kätevä työkalu, jolla voit laskea koodisi tehokkuuden.





Mikä on Big-O-merkintä?

Big-O-merkintä antaa sinulle tavan laskea kuinka kauan koodin suorittaminen kestää. Voit fyysisesti määrittää, kuinka kauan koodisi kestää, mutta tällä menetelmällä on vaikea havaita pieniä aikaeroja. Esimerkiksi 20–50 koodirivin suorittamiseen kuluva aika on hyvin lyhyt. Kuitenkin suuressa ohjelmassa nämä tehottomuudet voivat kasvaa.



kopioi video verkkosivustolta

Big-O-merkintä laskee kuinka monta vaihetta algoritmin on suoritettava tehokkuutensa mittaamiseksi. Koodin 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 suoritettavien vaiheiden lukumäärän perusteella ja verrata algoritmien tehokkuutta objektiivisesti.





Kuinka lasket Big-O-merkintätavat?

Tarkastellaan kahta toimintoa, jotka laskevat kuinka monta yksittäistä sukkia on laatikossa. Kukin toiminto ottaa sukkaparien määrän ja palauttaa yksittäisten sukkien määrän. Koodi on kirjoitettu Pythonilla, mutta se ei vaikuta siihen, kuinka laskemme vaiheiden määrän.

Algoritmi 1:



def sockCounter(numberOfPairs):
individualSocks = 0
for x in range(numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

Algoritmi 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Tämä on typerä esimerkki, ja sinun pitäisi pystyä helposti kertomaan, mikä algoritmi on tehokkaampi. Mutta harjoitellaan, käydään jokainen läpi.



LIITTYVÄT: Mikä on toiminto ohjelmoinnissa?

Algoritmissa 1 on monia vaiheita:



  1. Se määrittää muuttujalle individualSocks arvon nolla.
  2. Se antaa muuttujalle i yhden arvon.
  3. Se vertaa i: n arvoa numeroonOfPairs.
  4. Se lisää kaksi IndividualSocksiin.
  5. Se määrittää yksittäisten sukkien lisääntyneen arvon itselleen.
  6. Se kasvaa i kerrallaan.
  7. Sitten se palaa vaiheiden 3-6 läpi saman määrän kertoja kuin (indiviualSocks - 1).

Vaiheiden määrä, jotka meidän on suoritettava algoritmia varten, voidaan ilmaista seuraavasti:

4n + 2

Meidän on suoritettava neljä vaihetta n kertaa. Tässä tapauksessa n olisi yhtä suuri kuin numberOfPairs. On myös 2 vaihetta, jotka suoritetaan kerran.

Vertailun vuoksi algoritmilla 2 on vain yksi vaihe. NumberOfPairs -arvo kerrotaan kahdella. Ilmaisimme sen seuraavasti:

1

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

Big-O-analyysi

Yleensä, kun olet kiinnostunut algoritmin Big-O-merkinnöistä, olet enemmän kiinnostunut kokonaistehokkuudesta ja vähemmän vaiheiden määrän hienorakeisesta analyysistä. Merkintöjen yksinkertaistamiseksi voimme vain todeta tehokkuuden suuruuden.

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

O(1)

Mutta algoritmia 1 yksinkertaistettaisiin seuraavasti:

O(n)

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

Lineaarinen koodi

Kuva: Nick Fledderus/ Substantiiviprojekti

Koska emme tiedä n: n arvoa, on hyödyllisempää pohtia, kuinka n: n arvo vaikuttaa suoritettavan koodin määrään. Algoritmissa 1 voimme sanoa, että suhde on lineaarinen. Jos piirtät vaiheiden määrän vs. arvon n, saat suoran linjan, joka nousee.

Toisen asteen koodi

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

def searchForValue(targetValue, arraySearched):
foundTarget = False
for x in arraySearched:
for y in x:
if(y == targetValue):
foundTarget = True
return foundTarget

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

kuinka paljon netflix maksaa kuukaudessa

Kuva: Nick Fledderus/ Substantiiviprojekti

Tämä suhde on toisen asteen suhde, mikä tarkoittaa, että algoritmimme 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 tarkasteltava suhde on logaritminen. Muistin virkistämiseksi numeroloki on eksponentti -arvo, joka vaaditaan perusnumeron saavuttamiseksi. Esimerkiksi:

log 2 (8) = 3

Loki on kolme, koska jos kantamme olisi 2, tarvitsisimme eksponentti -arvon 3 päästäksemme numeroon 8.

Kuva: Nick Fledderus/ Substantiiviprojekti

Joten logaritmisen funktion suhde on eksponentiaalisen suhteen vastakohta. Kun n kasvaa, algoritmin suorittamiseen tarvitaan vähemmän uusia vaiheita.

Ensi silmäyksellä tämä vaikuttaa intuitiiviselta. Kuinka algoritmin vaiheet voivat kasvaa hitaammin kuin n? Hyvä esimerkki tästä on binaariset haut. Tarkastellaanpa algoritmia, jolla etsitään numero yksilöllisten arvojen joukosta.

  • Aloitamme haulla taulukolla, joka on järjestyksessä pienimmästä suurimpaan.
  • Seuraavaksi tarkistamme taulukon keskellä olevan arvon.
  • Jos numerosi on suurempi, suljemme pois pienemmät numerot haustamme ja jos numero oli pienempi, suljemme pois suuret numerot.
  • Katsomme nyt jäljellä olevien numeroiden keskimmäistä lukua.
  • Jälleen jätetään pois puolet luvuista sen perusteella, onko tavoitearvo keskiarvoa suurempi tai pienempi.
  • Jatkamme tätä prosessia, kunnes löydämme tavoitteemme tai toteamme, että se ei ole luettelossa.

Kuten näette, koska binaariset haut poistavat puolet mahdollisista arvoista jokaisen passin aikana, kun n kasvaa, vaikutus tuskin vaikuttaa siihen, kuinka monta kertaa tarkistamme taulukon. Voidaksemme ilmaista tämän Big-O-merkinnällä kirjoittaisimme:

O(log(n))

Big-O-merkintöjen merkitys

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

kuinka poistaa skype for business

Kun opit ensimmäistä kertaa koodaamaan, aloitat lineaarisista funktioista. Kuten yllä olevasta kaaviosta näet, pääset pitkälle. Mutta kun tulet kokeneemmaksi ja alat rakentaa monimutkaisempaa koodia, tehokkuudesta tulee ongelma. Ymmärtäminen koodin tehokkuuden määrittämisestä antaa sinulle työkalut, joiden avulla voit alkaa virittää sitä tehokkuuden parantamiseksi ja punnita algoritmien hyvät ja huonot puolet.

Jaa Jaa Tweet Sähköposti 10 Yleisimmät ohjelmointi- ja koodausvirheet

Koodausvirheet voivat aiheuttaa monia ongelmia. Nämä vinkit auttavat sinua välttämään ohjelmointivirheitä ja pitämään koodisi mielekkäänä.

Lue seuraava Liittyvät aiheet
  • Ohjelmointi
  • Ohjelmointi
Kirjailijasta Jennifer Seaton(21 artikkelia julkaistu)

J. Seaton on tiedekirjoittaja, joka on erikoistunut monimutkaisten aiheiden jakamiseen. Hänellä on tohtori Saskatchewanin yliopistosta; hänen tutkimuksensa keskittyi pelipohjaisen oppimisen hyödyntämiseen opiskelijoiden sitoutumisen lisäämiseksi verkossa. Kun hän ei työskentele, löydät hänet lukemisen, videopelien tai puutarhanhoidon kanssa.

Lisää Jennifer Seatonilta

tilaa uutiskirjeemme

Liity uutiskirjeeseemme saadaksesi teknisiä vinkkejä, arvosteluja, ilmaisia ​​e -kirjoja ja ainutlaatuisia tarjouksia!

Klikkaa tästä tilataksesi