Viskas, ką jums reikia žinoti apie „Big O Notation“, kad įvyktų kitas interviu koduojant

Dalyvaudamas programinės įrangos kūrimo švietime, turėjau kaupti įgūdžius įvairiose srityse, kad galėčiau būti visiškai pasirengęs pirmajai programinės įrangos pozicijai. Į bet kokią druskos vertą programinės įrangos mokymo programą bus įtraukta nemaža dalis mokymo programos, skirtos pasiruošti liūdnai pagarsėjusiam kodavimo interviu.

Taigi kiekvienos dienos pradžioje aš dirbu spręsdamas algoritmus, nes tai yra pagrindinė ( daugeliui sunkiausių ) daugelio kodavimo interviu dalis.

Vienas dalykas, su kuriuo susidūriau dirbdamas su kompiuterių algoritmais, yra tai, kas vadinama „Big O Notation“ .

Tai gana abstrakti ir labai ezoterinė koncepcija, apie kurią didžioji dauguma žmonių niekada neišgirs ir nerūpės. BET tai žinoma kaip įprastas interviu kodavimo klausimas , todėl tai yra vienas iš dalykų, kuriuos praleidau tam tikrą laiką mokydamasis.

Ką tu turi žinoti

Štai ką įsisavinau norėdamas pasiruošti pats

Norėdami nustatyti „Big O“ sceną, pirmiausia turime pripažinti, kad programinė įranga, be abejo, labai pagrįsta duomenimis . Didžiuliai duomenų kalnai. Kodavimas yra tų duomenų panaudojimas. Kad programa galėtų naudoti duomenis, ji dažnai turi pradėti nuo duomenų rūšiavimo pagal loginę tvarką. Nesvarbu, ar tai yra abėcėlės, chronologijos, dydžio, datos ir pan.

Rūšiavimas vyksta NUOLATINIAI ir iš tikrųjų sudaro didžiulę dalį kompiuterio ir interneto veiklos. Girdėjau programuotojus sakant, kad „Greitasis rūšiavimas yra beveik tas, kuris valdo visą internetą“.

Ką jie tuo nori pasakyti? Duomenų rūšiavimas yra visas jos pačios poskyris kompiuterių mokslo tyrime, ir yra daug gerai apibrėžtų rūšiavimo algoritmų. Yra greitas rūšiavimas, burbulų rūšiavimas, atrankos rūšiavimas, sujungimo rūšiavimas, kaupo rūšiavimas ir daug kitų. Kiekvienas turi skirtingą požiūrį, kad pasiektų tuos pačius ar panašius rezultatus.

Bet kuris iš jų yra geriausias, jei jie (beveik) visi duoda tą patį rezultatą?

Geriausias paprastai reiškia greičiausią. Čia atsirado „Big O“.

„Big O“ žymėjimas, kartais dar vadinamas „asimptotine analize“, pirmiausia žiūri, kiek operacijų reikia rūšiavimo algoritmui, norint visiškai surūšiuoti labai didelį duomenų rinkinį. Tai yra efektyvumo matas ir tai, kaip galite tiesiogiai palyginti vieną algoritmą su kitu.

Kuriant paprastą programą, kurioje būtų naudojami tik keli duomenys, tokios analizės atlikti nereikia. Tačiau dirbant su labai dideliu duomenų kiekiu, pvz., Socialinės žiniasklaidos svetaine ar didele elektroninės prekybos svetaine, kurioje yra daug klientų ir produktų, nedideli algoritmų skirtumai gali būti reikšmingi.

Didelis O žymėjimas reitinguoja algoritmų efektyvumą

Tai daro „ O “ ir „ n “ atžvilgiu (pavyzdys: „ O (log n)“) , kur

  • O reiškia funkcijos eilę arba jos augimo greitį ir
  • n yra rūšiuojamo masyvo ilgis.

Panagrinėkime pavyzdį. Jei algoritme yra reikalingų operacijų skaičiaus formulė:

f (n) = 6n ^ 4 - 2n ^ 3 + 5

Kai „ n “ artėja prie begalybės (labai dideliems duomenų rinkiniams), iš trijų esančių terminų svarbu tik 6n ^ 4 . Taigi mažesnieji terminai 2n ^ 3 ir 5 iš tikrųjų yra tiesiog praleisti, nes jie yra nereikšmingi. Tas pats pasakytina apie „ 6 “, esantį 6n ^ 4 .

Todėl ši funkcija turėtų O (n ^ 4) eilės augimo tempą arba „didelio O“ reitingą.

Žvelgdami į daugelį dažniausiai naudojamų rūšiavimo algoritmų,Reitingų O (N log N) apskritai yra geriausia, kad gali būti pasiektas. Algoritmai, kurie veikia pagal šį reitingą, yra greitasis rūšiuoti, kaupti ir kaupti. Greitasis rūšiavimas yra standartas ir naudojamas kaip numatytasis beveik visomis programinės įrangos kalbomis.

Svarbu pažymėti, kad nėra vieno algoritmo, kuris būtų greičiausias visais atvejais , nes duomenis į programą galima įvesti visomis būsenomis. Kiekvieno algoritmo požiūriai turės geriausią ir blogiausią scenarijų, kai jie veikia geriausiu ar blogiausiu atveju.

Nors „Quick Sort“ yra standartas, jis taip pat konkuruoja su „Merge Sort“ ir „Heap Sort“, kurie yra kiti O (n log n) įvertinti rūšiavimo algoritmai. Yra scenarijų, kai jie naudojami vietoj jų.

Tiesioginis „Quick Sort“ konkurentas yra „ Heap Sort“. „Heap Sort“ veikimo laikas taip pat yra O (n log n), tačiau „Heap Sort“ vidutinis veikimo laikas paprastai laikomas lėtesniu nei „Quick Sort“.

„Merge Sort“ yra stabili rūšiavimo rūšis , o tai reiškia, kad išvestyje išsaugoma vienodų elementų įvesties tvarka, skirtingai nei standartiniai vietoje esantys „Quick Sort“ ir „Heap Sort“.

„Bubble / Insertion / Selection“ rūšiavimas vykdomas O (n²) , kuris, kalbant apie didelius duomenis , operacijų skaičiumi gali užtrukti žymiai ilgiau nei aukščiau išvardytieji, įvertinti O (n log n). Tačiau gali būti scenarijų, kai kiti yra greitesni, priklausomai nuo duomenų.

Taip pat yra atvejų, kai kažkas labai paprasto, pavyzdžiui, „Rūšiuoti skaičiuojant“, yra puiku, nes jį užrašyti yra daug greičiau, o jį lengviau įsivaizduoti ir suprasti.

Kai kada reikia atsižvelgti ne tik į algoritmo laiko poreikius, bet ir į duomenų erdvės poreikius (o gal net labiau). Kai kurie algoritmai taip pat veikia su mažesniu saugyklos plotu.

Kodėl visa tai reikia žinoti?

Taigi po visko, jei jūs visada naudojatės tik kalbos integruotu rūšiavimo algoritmu (kuris pagrįstas greituoju rūšiavimu), tai kam rūpintis algoritmų rūšiavimu ir „Big O“? Kodėl įmonės interviu metu jūsų apie tai klaustų?

Atsakymas yra tas, kad studijuodamas „Big O“ žymėjimą supranti savo kode labai svarbią efektyvumo sampratą. Taigi dirbdami su didžiuliais duomenų rinkiniais gerai suprasite, kur dėl didelių sulėtėjimų greičiausiai atsiras kliūčių ir kur reikėtų skirti daugiau dėmesio, kad būtų pasiekti didžiausi patobulinimai. Tai taip pat vadinama jautrumo analize ir yra svarbi problemų sprendimo ir puikios programinės įrangos rašymo dalis.

Taigi, jei bandote pasiruošti savo pirmajam pokalbiui, o galbūt stengėtės paskutiniame, padidinsite savo žinias tokiomis sąvokomis kaip „Big O Notation“ ir kitomis informatikos temomis. Jūs būsite geriau pasirengę pademonstruoti savo galimybes ir padaryti įspūdį, kad nusileisite šioje pozicijoje.