Mis on Big-O tähistamine?

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 tähistamine on mugav tööriist teie koodi tegelikult tõhususe arvutamiseks.

Mis on Big-O tähistamine?

Big-O tähistamine annab teile võimaluse arvutada, kui kaua kulub teie koodi käitamiseks. Füüsiliselt saate määrata, kui kaua teie kood käivitamiseks kulub, kuid selle meetodi abil on raske väikseid ajaerinevusi tabada. Näiteks 20–50 koodirea käitamise vahel kuluv aeg on väga väike. Suures programmis võivad need ebaefektiivsused siiski kokku tulla.

Big-O tähistamine loeb mitu sammu peab algoritm selle efektiivsuse hindamiseks tegema. Sel viisil oma koodile lähenemine võib olla väga tõhus, kui peate oma koodi tõhususe suurendamiseks häälestama. Big-O tähistamine võimaldab mõõta erinevaid algoritme selle käivitamiseks vajalike sammude arvu järgi ja objektiivselt võrrelda algoritmide efektiivsust.

Kuidas arvutada Big-O tähistust

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

Algoritm 1:

def sockCounter (numberOfPairs):
individualSocks = 0
x vahemikus (numberOfPairs):
individualSocks = individualSocks + 2
tagastage individualSocks

2. algoritm:

def sockCounter (numberOfPairs):
tagastamise numberOfPairs * 2

See on rumal näide ja peaksite saama hõlpsasti öelda, milline algoritm on tõhusam. Kuid harjutamiseks jookseme igaüks läbi.

SEOTUD: Mis on funktsioon programmeerimisel?

Mis on funktsioon programmeerimisel?

Kui õpite oma koodi programmeerima, peate mõistma, millised funktsioonid on.

Algoritmil 1 on palju samme:

1. See määrab muutujale individualSocks nulli väärtuse.
2. See määrab muutujale i ühe väärtuse.
3. See võrdleb i väärtust numberOfPairsiga.
4. See lisab individuaalsetele sokkidele kaks.
5. See määrab individuaalse soki suurema väärtuse endale.
6. See suurendab i ühe võrra.
7. Seejärel liigutakse tagasi samme 3 kuni 6 sama palju kordi kui (indiviualSocks - 1).

Esimese algoritmi jaoks sooritatavate sammude arvu võib väljendada järgmiselt:

4n + 2

On neli sammu, mille peame täitma n korda. Sel juhul võrduks n väärtus numberOfPairs. Samuti on 2 sammu, mis viiakse lõpule üks kord.

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

1

Kui see polnud veel ilmne, näeme nüüd hõlpsasti, et algoritm 2 on üsna palju tõhusam.

Big-O analüüs

Üldiselt, kui teid huvitab algoritmi Big-O tähistamine, siis rohkem huvitab üldine efektiivsus ja vähem sammude arvu peeneteraline analüüs. Märgistuse lihtsustamiseks võime lihtsalt öelda efektiivsuse suuruse.

Eespool toodud näidetes väljendataks algoritmi 2 ühena:

O (1)

Kuid algoritmi 1 lihtsustatakse järgmiselt:

Peal)

See kiire ülevaade ütleb meile, kuidas algoritmi efektiivsus on seotud n väärtusega. Mida suurem on number, seda rohkem tuleb algoritmi täita.

Lineaarne kood

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 koostate sammude arvu vs. n väärtusega saate sirgjoone, mis läheb üles.

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 sellise algoritmi:

def searchForValue (targetValue, arraySearched):
foundTarget = Vale
massiivi jaoks x-le otsitud:
y jaoks x:
kui (y == targetValue):
foundTarget = Tõsi
return foundTarget

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

See seos on ruutkordaja, mis tähendab, et meie algoritmi sammude arv kasvab n-ga plahvatuslikult. Big-O noodis 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 vaatame, logaritmilised suhted. Mälu värskendamiseks on numbri logi eksponendi väärtus, mis on vajalik baasi saanud numbri saavutamiseks. Näiteks:

log 2 (8) = 3

Logi võrdub kolmega, sest kui meie alus oleks 2, vajaksime arvu 8 juurde jõudmiseks eksponendi väärtust 3.

Niisiis, logaritmilise funktsiooni suhe on vastupidine eksponentsiaalsele suhtele. Kui n suureneb, on algoritmi käitamiseks vaja vähem uusi samme.

Esmapilgul tundub see vastu-intuitiivne. Kuidas saavad algoritmi sammud kasvada aeglasemalt kui n? Hea näide sellest on kahendotsingud. Vaatleme algoritmi arvu otsimiseks unikaalsete väärtuste massiivist.

• Alustame massiivi otsimiseks, mis on väikseima ja suurima järjekorras.
• Järgmisena kontrollime väärtust massiivi keskel.
• Kui teie arv on suurem, välistame otsingus madalamad numbrid ja kui arv oli väiksem, välistame suuremad numbrid.
• Nüüd vaatame ülejäänud numbrite keskmist arvu.
• Jällegi välistame pooled arvud selle põhjal, kas meie sihtväärtus on keskmisest suurem või väiksem.
• Jätkame seda protsessi seni, kuni leiame oma sihtmärgi või tuvastame, et seda pole loendis.

Nagu näete, kuna binaarotsingud välistavad igal läbimisel pooled võimalikest väärtustest, kui n suureneb, mõjutab see massiivi kontrollimiste arvu vaevu. Selle väljendamiseks Big-O tähistuses kirjutaksime:

O (log (n))

Big-O märkimise tähtsus

Big-O riik annab teile kiire ja lihtsa viisi algoritmi tõhususe edastamiseks. Nii on erinevate algoritmide vahel otsustamine lihtsam. See võib olla eriti kasulik, kui kasutate teegi algoritmi ega tea tingimata, kuidas kood välja näeb.

Esmakordselt kodeerima õppides alustate lineaarsetest funktsioonidest. Nagu ülaltoodud graafikult näha, viib see teid väga kaugele. Kuid kui olete kogenum ja hakkate keerukamat koodi üles ehitama, hakkab efektiivsus muutuma probleemiks. Mõistmine, kuidas oma koodi tõhusust kvantifitseerida, annab teile tööriistad, mis on vajalikud selle tõhususe häälestamiseks ja algoritmide plusse ja miinuseid kaalumiseks.

10 kõige tavalisemat programmeerimis- ja kodeerimisviga

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

Autori kohta