Mis on Big-O märge?

Mis on Big-O märge?

Kas olete kunagi mõelnud, miks teie kirjutatud programmi käivitamine nii kaua aega võttis? Võib -olla soovite teada, kas saate oma koodi tõhusamaks muuta. Koodi käitamise mõistmine võib viia teie koodi järgmisele tasemele. Big-O märge on mugav tööriist teie koodi tegeliku tõhususe arvutamiseks.





Mis on Big-O märge?

Big-O märge annab teile võimaluse arvutada, kui kaua kulub teie koodi käitamiseks. Saate koodi käivitamiseks füüsiliselt aega määrata, kuid selle meetodi abil on väikseid ajalisi erinevusi raske tabada. Näiteks aeg, mis kulub 20–50 koodirida käivitamiseks, on väga väike. Kuid suures programmis võivad need ebatõhusused kokku liituda.



ootamatu kerneli režiimi lõks Windows 10

Märkus Big-O loeb, mitu sammu peab algoritm oma tõhususe hindamiseks sooritama. Sellisel viisil oma koodile lähenemine võib olla väga tõhus, kui peate tõhususe suurendamiseks koodi häälestama. Big-O märge võimaldab teil mõõta erinevaid algoritme käivitamiseks vajalike sammude arvu järgi ja võrrelda algoritmide tõhusust objektiivselt.





Kuidas arvutada Big-O märge

Vaatleme kahte funktsiooni, mis loevad, kui palju üksikuid sokke sahtlis on. Iga funktsioon võtab sokipaaride arvu ja tagastab üksikute sokkide arvu. Kood on kirjutatud Pythonis, kuid see ei mõjuta sammude arvu loendamist.

Algoritm 1:



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

Algoritm 2:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

See on rumal näide ja teil peaks olema lihtne öelda, milline algoritm on tõhusam. Kuid harjutamiseks jookseme igaüks läbi.



SEOTUD: Mis on programmeerimise funktsioon?

Algoritmil 1 on palju samme:



  1. See määrab muutujale individualSocks väärtuse null.
  2. See määrab muutujale i väärtuse üks.
  3. See võrdleb i väärtust numberOfPairsiga.
  4. See lisab individuaalsetele sokkidele kaks.
  5. See määrab individualSocksi suurenenud väärtuse endale.
  6. See suurendab i ühe võrra.
  7. Seejärel liigub see sammuga 3–6 tagasi sama palju kordi kui (indiviualSocks - 1).

Algoritmi jaoks täidetavate sammude arvu saab väljendada järgmiselt:

4n + 2

Meil on neli sammu, mida peame täitma n korda. Sel juhul võrduks n arvuga numberOfPairs. Samuti on kaks toimingut, mis viiakse läbi üks kord.

Võrdluseks, algoritmil 2 on vaid üks samm. NumberOfPairs väärtus korrutatakse kahega. Me väljendaksime seda järgmiselt:

1

Kui see ei olnud juba ilmne, näeme nüüd hõlpsalt, et algoritm 2 on üsna palju tõhusam.

Big-O analüüs

Üldiselt, kui olete huvitatud algoritmi Big-O märgistamisest, olete rohkem huvitatud üldisest efektiivsusest ja vähem sammude arvu peeneteralisest analüüsist. Märkimise lihtsustamiseks võime lihtsalt öelda tõhususe suuruse.

Ülaltoodud näidetes väljendatakse algoritmi 2 järgmiselt:

O(1)

Kuid algoritmi 1 lihtsustatakse järgmiselt:

O(n)

See kiire ülevaade ütleb meile, kuidas ühe algoritmi efektiivsus on seotud väärtusega n. Mida suurem number, seda rohkem samme peab algoritm täitma.

Lineaarne kood

Pildikrediit: Nick Fledderus/ Nimisõna projekt

Kuna me ei tea n väärtust, on kasulikum mõelda, kuidas n väärtus mõjutab käivitatava koodi hulka. Algoritmis 1 võime öelda, et seos on lineaarne. Kui joonistate sammude arvu ja väärtuse n, saate sirgjoone, mis tõuseb.

Ruutkood

Kõik suhted pole nii lihtsad kui lineaarne näide. Kujutage ette, et teil on 2D -massiiv ja soovite massiivist väärtust otsida. Võite luua järgmise algoritmi:

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

Selles näites sõltub sammude arv massiivide arvust arraySearched ja väärtuste arvust igas massiivis. Seega oleks lihtsustatud sammude arv n * n või n².

kaks arvutit kaks monitori üks klaviatuur üks hiir

Pildikrediit: Nick Fledderus/ Nimisõna projekt

See seos on ruutkeste, mis tähendab, et sammude arv meie algoritmis kasvab eksponentsiaalselt koos n -ga. Big-O märkides kirjutaksite selle järgmiselt:

O(n²)

SEOTUD: Kasulikud tööriistad CSS -failide kontrollimiseks, puhastamiseks ja optimeerimiseks

Logaritmiline kood

Kuigi on palju muid suhteid, on viimane suhe, mida me vaatame, logaritmilised suhted. Mälu värskendamiseks on numbri logi astendav väärtus, mis on vajalik alusele antud numbri saavutamiseks. Näiteks:

log 2 (8) = 3

Logi võrdub kolmega, sest kui meie baas oleks 2, vajaksime arvu 8 saamiseks eksponentväärtust 3.

Pildikrediit: Nick Fledderus/ Nimisõna projekt

Niisiis, logaritmilise funktsiooni suhe on eksponentsiaalse suhte vastand. Kui n suureneb, on algoritmi käitamiseks vaja vähem uusi samme.

Esmapilgul tundub see intuitiivne. Kuidas saavad algoritmi sammud kasvada aeglasemalt kui n? Hea näide sellest on binaarotsingud. Vaatleme algoritmi, et otsida numbrit unikaalsete väärtuste massiivist.

  • Alustame otsimiseks massiiviga, mis on järjestuses väikseimast suurimani.
  • Järgmisena kontrollime massiivi keskel asuvat väärtust.
  • Kui teie arv on suurem, välistame otsingust madalamad numbrid ja kui number oli väiksem, välistame kõrgemad numbrid.
  • Nüüd vaatame ülejäänud numbrite keskmist numbrit.
  • Jällegi jätame pooled numbrid välja selle põhjal, kas meie sihtväärtus on keskmisest suurem või väiksem.
  • Jätkame seda protsessi, kuni leiame oma sihtmärgi või teeme kindlaks, et seda pole loendis.

Nagu näete, kuna binaarotsingud kõrvaldavad pooled võimalikest väärtustest igal läbimisel, kui n suureneb, mõjutab see massiivi kontrollimiste arvu vaevalt. Selle väljendamiseks Big-O märkusena kirjutaksime:

O(log(n))

Big-O märke tähtsus

Big-O nation pakub teile kiiret ja lihtsat viisi algoritmi tõhususe edastamiseks. Nii on lihtsam otsustada erinevate algoritmide vahel. See võib olla eriti kasulik, kui kasutate teegist pärit algoritmi ega tea tingimata, milline kood välja näeb.

kuidas korraldada raamatuid Kindle'i rakenduses

Kui te esimest korda kodeerimist õppite, alustate lineaarsete funktsioonidega. Nagu ülaltoodud graafikult näha, jõuate sellega väga kaugele. Kuid kui olete kogenum ja hakkate keerukamat koodi koostama, hakkab tõhusus muutuma probleemiks. Oma koodi tõhususe kvantifitseerimise mõistmine annab teile vajalikud tööriistad selle tõhususe häälestamiseks ning algoritmide plusside ja miinuste kaalumiseks.

Jaga Jaga Piiksuma E -post 10 levinumat programmeerimis- ja kodeerimisviga

Kodeerimisvead võivad põhjustada nii palju probleeme. Need näpunäited aitavad teil vältida programmeerimisvigu ja hoida oma koodi tähendusrikkana.

Loe edasi Seotud teemad
  • Programmeerimine
  • Programmeerimine
Autori kohta Jennifer Seaton(Avaldatud 21 artiklit)

J. Seaton on teaduskirjanik, kes on spetsialiseerunud keeruliste teemade lõhkumisele. Tal on doktorikraad Saskatchewani ülikoolist; tema uurimus keskendus mängupõhise õppe kasutamisele õpilaste veebipõhise kaasamise suurendamiseks. Kui ta ei tööta, leiad ta koos temaga lugemise, videomängude mängimise või aiandusega.

Veel Jennifer Seatonilt

Telli meie uudiskiri

Liituge meie uudiskirjaga, et saada tehnilisi näpunäiteid, ülevaateid, tasuta e -raamatuid ja eksklusiivseid pakkumisi!

Tellimiseks klõpsake siin