Kas ir Big-O apzīmējums?

Kas ir Big-O apzīmējums?

Vai esat kādreiz domājuši, kāpēc jūsu uzrakstītās programmas palaišana prasīja tik ilgu laiku? Varbūt vēlaties uzzināt, vai varat padarīt savu kodu efektīvāku. Izpratne par koda izpildi var paaugstināt jūsu kodu nākamajā līmenī. Big-O apzīmējums ir ērts rīks, lai aprēķinātu, cik efektīvs ir jūsu kods.





Kas ir Big-O apzīmējums?

Big-O apzīmējums sniedz iespēju aprēķināt, cik ilgs laiks būs nepieciešams, lai palaistu kodu. Jūs varat fiziski noteikt, cik ilgs laiks nepieciešams jūsu koda palaišanai, taču, izmantojot šo metodi, ir grūti pamanīt nelielas laika atšķirības. Piemēram, laiks, kas nepieciešams starp 20 un 50 koda rindu izpildi, ir ļoti mazs. Tomēr lielā programmā šīs neefektivitātes var palielināties.



kā paātrināt internetu tālrunī

Big-O apzīmējums skaita, cik soļu algoritmam ir jāizpilda, lai novērtētu tā efektivitāti. Šāda pieeja jūsu kodam var būt ļoti efektīva, ja jums ir jāpielāgo kods, lai palielinātu efektivitāti. Big-O apzīmējums ļaus jums izmērīt dažādus algoritmus pēc palaišanas soļu skaita un objektīvi salīdzināt algoritmu efektivitāti.





Kā aprēķināt lielos apzīmējumus

Apsvērsim divas funkcijas, kas saskaita, cik atsevišķu zeķu ir atvilktnē. Katra funkcija ņem zeķu pāru skaitu un atgriež atsevišķu zeķu skaitu. Kods ir rakstīts Python, taču tas neietekmē to, kā mēs skaitītu soļu skaitu.

1. algoritms:



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

2. algoritms:

def sockCounter(numberOfPairs):
return numberOfPairs * 2

Šis ir dumjš piemērs, un jums vajadzētu būt iespējai viegli pateikt, kurš algoritms ir efektīvāks. Bet praksei, ieskrienam katram cauri.



SAISTĪTI: Kas ir funkcija programmēšanā?

Pirmajam algoritmam ir daudz soļu:



  1. Tas piešķir nullei vērtību mainīgajam individualSocks.
  2. Tas piešķir mainīgajam i vērtību vienu.
  3. Tas salīdzina i vērtību ar numberOfPairs.
  4. IndividualSocks tas pievieno divus.
  5. Tā piešķir individuālās zeķes paaugstinātu vērtību sev.
  6. Tas palielina i par vienu.
  7. Pēc tam tas atgriežas, veicot 3. līdz 6. darbību tikpat reižu kā (indiviualSocks - 1).

Pirmo algoritmu veikto darbību skaitu var izteikt šādi:

4n + 2

Ir četras darbības, kas mums jāizpilda n reizes. Šajā gadījumā n būtu vienāds ar numberOfPairs vērtību. Ir arī 2 darbības, kas tiek veiktas vienu reizi.

Salīdzinājumam, algoritmam 2 ir tikai viens solis. NumberOfPairs vērtība tiek reizināta ar diviem. Mēs to izteiktu šādi:

1

Ja tas vēl nebija redzams, mēs tagad varam viegli redzēt, ka 2. algoritms ir par nedaudz efektīvāks.

Big-O analīze

Parasti, ja jūs interesē algoritma Big-O apzīmējums, jūs vairāk interesē kopējā efektivitāte un mazāk-soļu skaita smalko graudu analīze. Lai vienkāršotu apzīmējumus, mēs varam tikai norādīt efektivitātes lielumu.

Iepriekš minētajos piemēros 2. algoritms tiktu izteikts kā viens:

O(1)

Bet algoritms 1 tiks vienkāršots šādi:

O(n)

Šis ātrais momentuzņēmums mums parāda, kā pirmā algoritma efektivitāte ir saistīta ar vērtību n. Jo lielāks skaitlis, jo vairāk soļu algoritmam būs jāveic.

Lineārais kods

Attēlu kredīts: Nick Fledderus/ Lietvārdu projekts

Tā kā mēs nezinām n vērtību, ir lietderīgāk padomāt par to, kā n vērtība ietekmē izpildāmā koda daudzumu. 1. algoritmā mēs varam teikt, ka attiecības ir lineāras. Ja uzzīmējat soļu skaitu pret n vērtību, iegūstat taisnu līniju, kas iet uz augšu.

Kvadrātiskais kods

Ne visas attiecības ir tik vienkāršas kā lineārais piemērs. Iedomājieties, ka jums ir 2D masīvs un vēlaties masīvā meklēt vērtību. Jūs varat izveidot šādu algoritmu:

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

Šajā piemērā soļu skaits ir atkarīgs no masīvu skaita masīvā un meklētajām vērtībām katrā masīvā. Tātad vienkāršotais soļu skaits būtu n * n vai n².

virtuālā atmiņa windows 10 16gb ram

Attēlu kredīts: Nick Fledderus/ Lietvārdu projekts

Šīs attiecības ir kvadrātiskas attiecības, kas nozīmē, ka soļu skaits mūsu algoritmā pieaug eksponenciāli līdz ar n. Lielajā apzīmējumā jūs to rakstītu šādi:

O(n²)

SAISTĪTI: Noderīgi rīki CSS failu pārbaudei, tīrīšanai un optimizēšanai

Logaritmiskais kods

Lai gan ir daudz citu attiecību, pēdējās attiecības, kuras mēs apskatīsim, ir logaritmiskās attiecības. Lai atsvaidzinātu atmiņu, skaitļa žurnāls ir eksponenta vērtība, kas nepieciešama, lai sasniegtu skaitli, kam dota bāze. Piemēram:

log 2 (8) = 3

Žurnāls ir vienāds ar trim, jo, ja mūsu bāze būtu 2, mums būtu nepieciešama eksponenta vērtība 3, lai iegūtu skaitli 8.

Attēlu kredīts: Nick Fledderus/ Lietvārdu projekts

Tātad logaritmiskās funkcijas attiecības ir pretējas eksponenciālām attiecībām. Palielinoties n, algoritma izpildei ir nepieciešams mazāk jaunu darbību.

No pirmā acu uzmetiena tas šķiet pretēji intuitīvam. Kā algoritma soļi var pieaugt lēnāk nekā n? Labs piemērs tam ir binārie meklējumi. Apskatīsim algoritmu, lai meklētu skaitli unikālu vērtību masīvā.

  • Mēs sāksim ar meklēšanas masīvu, kas ir no mazākā līdz lielākajam.
  • Tālāk mēs pārbaudīsim vērtību masīva vidū.
  • Ja jūsu skaitlis ir lielāks, mēs meklēšanas rezultātos izslēgsim zemākos skaitļus, un, ja skaitlis bija mazāks, mēs izslēgsim augstākos skaitļus.
  • Tagad mēs apskatīsim atlikušo skaitļu vidējo skaitli.
  • Atkal mēs izslēgsim pusi no skaitļiem, pamatojoties uz to, vai mūsu mērķa vērtība ir augstāka vai zemāka par vidējo vērtību.
  • Mēs turpināsim šo procesu, līdz atradīsim savu mērķi vai noskaidrosim, ka tas nav sarakstā.

Kā redzat, tā kā binārie meklējumi novērš pusi no iespējamām vērtībām katru reizi, kad n kļūst lielāks, ietekme uz masīva pārbaudes reižu skaitu tik tikko netiek ietekmēta. Lai to izteiktu Big-O apzīmējumā, mēs rakstītu:

O(log(n))

Liela apzīmējuma nozīme

Big-O nācija sniedz ātru un vienkāršu veidu, kā paziņot, cik efektīvs ir algoritms. Tas atvieglo izvēli starp dažādiem algoritmiem. Tas var būt īpaši noderīgi, ja izmantojat bibliotēkas algoritmu un ne vienmēr zināt, kā izskatās kods.

kā palaist lietas kā administratoram

Kad jūs pirmo reizi iemācāties kodēt, jūs sākat ar lineārām funkcijām. Kā redzat iepriekš redzamajā grafikā, tas jūs novedīs ļoti tālu. Bet, kad jūs kļūstat pieredzējis un sākat veidot sarežģītāku kodu, efektivitāte sāk kļūt par problēmu. Izpratne par to, kā noteikt koda efektivitāti, sniegs jums nepieciešamos rīkus, lai sāktu tā pielāgošanu efektivitātei un izsvērtu algoritmu plusus un mīnusus.

Kopīgot Kopīgot Čivināt E -pasts 10 izplatītākās programmēšanas un kodēšanas kļūdas

Kodēšanas kļūdas var radīt tik daudz problēmu. Šie padomi palīdzēs izvairīties no programmēšanas kļūdām un saglabāt kodu nozīmīgu.

Lasīt Tālāk Saistītās tēmas
  • Programmēšana
  • Programmēšana
Par autoru Dženifera Sītone(Publicēti 21 raksti)

J. Seaton ir zinātnes rakstnieks, kas specializējas sarežģītu tēmu sadalīšanā. Viņai ir doktora grāds Saskačevanas Universitātē; viņas pētījums bija vērsts uz spēlēm balstītas mācīšanās izmantošanu, lai palielinātu studentu iesaistīšanos tiešsaistē. Kad viņa nestrādā, jūs atradīsit viņu kopā ar lasīšanu, videospēļu spēlēšanu vai dārzkopību.

Vairāk no Dženiferas Sītones

Abonējiet mūsu biļetenu

Pievienojieties mūsu informatīvajam izdevumam, lai iegūtu tehniskus padomus, pārskatus, bezmaksas e -grāmatas un ekskluzīvus piedāvājumus!

Noklikšķiniet šeit, lai abonētu