Kas yra „Big-O“ žymėjimas?

Ar kada pagalvojote, kodėl jūsų parašytą programą reikėjo paleisti taip ilgai? Galbūt norėtumėte sužinoti, ar galite padaryti savo kodą efektyvesnį. Suprasti, kaip veikia kodas, gali perkelti jūsų kodą į kitą lygį. „Big-O“ žymėjimas yra patogus įrankis norint apskaičiuoti, koks iš tikrųjų yra jūsų kodas.

Kas yra „Big-O“ žymėjimas?

„Big-O“ žymėjimas suteikia galimybę apskaičiuoti, per kiek laiko reikės paleisti kodą. Galite fiziškai nustatyti, kiek laiko jūsų kodas užtrunka, tačiau taikant šį metodą sunku sugauti nedidelius laiko skirtumus. Pavyzdžiui, laikas, kurio reikia tarp 20–50 kodo eilučių, yra labai mažas. Tačiau didelėje programoje tas neefektyvumas gali prisidėti.

„Big-O“ žymėjimas skaičiuoja, kiek žingsnių turi atlikti algoritmas, kad įvertintų jo efektyvumą. Tokiu būdu prieiti prie jūsų kodo gali būti labai efektyvu, jei jums reikia sureguliuoti kodą, kad padidintumėte efektyvumą. „Big-O“ žymėjimas leis jums išmatuoti skirtingus algoritmus pagal atliktų veiksmų skaičių ir objektyviai palyginti algoritmų efektyvumą.

Kaip apskaičiuoti „Big-O“ žymėjimą

Panagrinėkime dvi funkcijas, kurios suskaičiuoja, kiek individualių kojinių yra stalčiuje. Kiekviena funkcija ima kojinių porų skaičių ir pateikia atskirų kojinių skaičių. Kodas parašytas „Python“, tačiau tai neturi įtakos tam, kaip suskaičiuotume žingsnių skaičių.

1 algoritmas:

def sockCounter (numberOfPairs):
individualSocks = 0
x diapazone (numberOfPairs):
individualSocks = individualSocks + 2
grąžinti individualSocks

2 algoritmas:

def sockCounter (numberOfPairs):
grąžinimo numerisOfPairs * 2

Tai yra kvailas pavyzdys, ir jūs turėtumėte lengvai pasakyti, kuris algoritmas yra efektyvesnis. Bet dėl ​​praktikos paleiskime kiekvieną.

SUSIJĘS: Kas yra programavimo funkcija?

Kas yra programavimo funkcija?

Jei mokotės programuoti savo kodą, turėsite suprasti, kokios funkcijos yra.

1 algoritmas turi daugybę žingsnių:

1. Kintamajam individualSocks jis priskiria nulinę vertę.
2. Jis kintamajam i priskiria vienos reikšmę.
3. Palyginama i reikšmė su numberOfPairs.
4. Tai prideda du prie individualSocks.
5. Tai priskiria padidintą „individualSocks“ vertę sau.
6. Jis didina i po vieną.
7. Tada jis grįžta per 3–6 veiksmus tiek pat kartų, kiek (indiviualSocks - 1).

Pirmo algoritmo atliktinų veiksmų skaičių galima išreikšti taip:

4n + 2

Yra keturi žingsniai, kuriuos turime atlikti n kartų. Tokiu atveju n būtų lygus „numberOfPairs“ vertei. Taip pat yra 2 veiksmai, kurie atliekami vieną kartą.

Palyginimui, 2 algoritmas turi tik vieną žingsnį. „NumberOfPairs“ vertė padauginama iš dviejų. Tai galėtume išreikšti taip:

1

Jei tai dar nebuvo akivaizdu, dabar galime lengvai pamatyti, kad 2 algoritmas yra efektyvesnis.

„Big-O“ analizė

Paprastai, kai jus domina algoritmo „Big-O“ žymėjimas, jus labiau domina bendras efektyvumas, o mažiau - smulkių veiksmų analizė. Norėdami supaprastinti žymėjimą, galime tiesiog nurodyti efektyvumo dydį.

Aukščiau pateiktuose pavyzdžiuose 2 algoritmas būtų išreikštas vienu:

O (1)

Tačiau 1 algoritmas būtų supaprastintas taip:

O (n)

Šis greitas momentinis vaizdas nurodo, kaip vieno algoritmo efektyvumas yra susietas su n verte. Kuo didesnis skaičius, tuo daugiau žingsnių reikės atlikti algoritmui.

Linijinis kodas

Kadangi mes nežinome n vertės, naudingiau yra pagalvoti apie tai, kaip n reikšmė veikia kodo kiekį, kurį reikia paleisti. 1 algoritme galime pasakyti, kad ryšys yra tiesinis. Jei planuojate žingsnių skaičių vs. n reikšmę gausite tiesę, kuri eina aukštyn.

Kvadratinis kodas

Ne visi santykiai yra tokie paprasti, kaip tiesinis pavyzdys. Įsivaizduokite, kad turite 2D masyvą ir norite ieškoti masyvo vertės. Galite sukurti tokį algoritmą:

def searchForValue (targetValue, arraySearched):
foundTarget = Klaidinga
x masyvo ieškota:
y y x:
jei (y == targetValue):
foundTarget = Tiesa
return foundTarget

Šiame pavyzdyje žingsnių skaičius priklauso nuo masyvų skaičiaus „arraySearched“ ir kiekvieno masyvo verčių skaičiaus. Taigi, supaprastintas žingsnių skaičius būtų n * n arba n².

Šis ryšys yra kvadratinis santykis, o tai reiškia, kad mūsų algoritmo žingsnių skaičius eksponentiškai auga su n. „Big-O“ žymėjime parašysite taip:

O (n²)

SUSIJĘS: Naudingi įrankiai, skirti patikrinti, išvalyti ir optimizuoti CSS failus

Logaritminis kodas

Nors yra daugybė kitų santykių, paskutiniai santykiai, į kuriuos pažvelgsime, yra logaritminiai santykiai. Norint atnaujinti atmintį, skaičiaus žurnalas yra rodiklio reikšmė, reikalinga norint pasiekti skaičių, kuriam suteikta bazė. Pavyzdžiui:

log 2 (8) = 3

Žurnalas yra lygus trims, nes jei mūsų bazė būtų 2, mums reiktų 3 rodiklio reikšmės, kad patektume į skaičių 8.

Taigi, logaritminės funkcijos santykis yra priešingas eksponentiniam santykiui. Kai n didėja, algoritmui paleisti reikia mažiau naujų žingsnių.

Iš pirmo žvilgsnio tai atrodo priešinga. Kaip algoritmo žingsniai gali augti lėčiau nei n? Geras to pavyzdys yra dvejetainės paieškos. Apsvarstykime algoritmą, kaip ieškoti numerio unikalių reikšmių masyve.

• Pradėsime nuo masyvo, kad galėtume ieškoti nuo mažiausių iki didžiausių.
• Tada mes patikrinsime vertę masyvo viduryje.
• Jei jūsų skaičius didesnis, į paiešką neįtrauksime mažesnių skaičių, o jei skaičius buvo mažesnis, išskirsime ir didesnius skaičius.
• Dabar apžvelgsime vidurinį likusių skaičių skaičių.
• Vėlgi, mes išskirsime pusę skaičių pagal tai, ar mūsų tikslinė vertė yra didesnė ar mažesnė už vidurinę vertę.
• Tęsime šį procesą, kol rasime tikslą arba nustatysime, kad jo nėra sąraše.

Kaip matote, kadangi dvejetainės paieškos pašalina pusę galimų reikšmių kiekviename praėjime, nes n padidėja, poveikis tam, kiek kartų mes tikriname masyvą, beveik neturi įtakos. Norėdami tai išreikšti „Big-O“ užrašais, parašysime:

O (žurnalas (n))

Big-O žymėjimo svarba

„Big-O nation“ suteikia jums greitą ir paprastą būdą pranešti apie algoritmo efektyvumą. Tai leidžia lengviau apsispręsti tarp skirtingų algoritmų. Tai gali būti ypač naudinga, jei naudojate bibliotekos algoritmą ir nebūtinai žinote, kaip atrodo kodas.

Kai pirmą kartą moki koduoti, pradedi nuo tiesinių funkcijų. Kaip matote iš aukščiau pateikto grafiko, tai pasieks jus labai toli. Bet kai tampi labiau patyręs ir pradedi kurti sudėtingesnį kodą, efektyvumas pradeda tapti problema. Supratimas, kaip apskaičiuoti kodo efektyvumą, suteiks jums įrankių, reikalingų norint jį derinti, kad būtų efektyviau, ir pasverkite algoritmų pliusus ir minusus.

10 dažniausiai pasitaikančių programavimo ir kodavimo klaidų

Kodavimo klaidos gali sukelti tiek daug problemų. Šie patarimai padės išvengti programavimo klaidų ir išlaikyti kodą prasmingą.

Apie autorių