Järgmise kodeerimisintervjuu purustamiseks peate kõike teadma „Big O Notationi” kohta

Oma tarkvaraarendusalase hariduse osana pidin ma omandama oskused erinevates valdkondades, et olla täielikult valmis oma esimeseks tarkvara ametikohaks. Ja iga tarkvaraharidusprogramm, mis on nende soola väärt, sisaldab paraja osa õppekavast, mis on mõeldud kurikuulsaks kodeerimisintervjuuks valmistumiseks.

Nii et iga päev hakkan tegelema algoritmide lahendamisega, kuna see on enamus kodeerimisintervjuudest (ja paljude jaoks ka kõige keerulisem ).

Üks asi, millega olen arvutiteaduse algoritmide kallal kokku puutunud, on midagi, mida nimetatakse “Big O Notationiks” .

See on üsna abstraktne ja väga esoteeriline kontseptsioon, millest valdav enamus inimesi kunagi ei kuule ega hooli sellest. AGA see on tuntud kui levinud intervjuu kodeerimise küsimus ja seetõttu on see üks asi, mille kulutamiseks olen mõnda aega kulutanud.

Mida peate teadma

Siin on see, mida ma olen enda ettevalmistamiseks kasutanud

„Big O” stseeni seadmiseks peame kõigepealt tunnistama, et tarkvara põhineb muidugi suuresti andmetel . Hiiglaslikud andmemäed. Ja nende andmete kasutamine on kodeerimine. Selleks, et programm andmeid saaks kasutada, tuleb sageli alustada nende andmete loogilisse järjestusse sortimisest. Kas see on tähestikulises, kronoloogilises, suuruse, kuupäeva jne järgi.

Sorteerimine toimub PIDEVALT ja moodustab tegelikult suure osa kogu arvuti- ja Interneti-tegevusest. Olen kuulnud, et programmeerijad väidavad, et "Kiire sorteerimine on peaaegu kogu Interneti juhtimine".

Mida nad selle all mõtlevad? Kaevude sorteerimine on kogu tema enda alajaotis arvutiteaduse uurimisel ning sortimiseks on palju täpselt määratletud algoritme. Valikus on kiire sortimine, mullide sorteerimine, valiku sortimine, ühendamise sortimine, kuhjaga sortimine ja palju muud. Igaühel on erinev lähenemine samade või sarnaste tulemuste saamiseks.

Kuid milline neist on parim, kui nad (peaaegu) kõik annavad sama tulemuse?

Parim tähendab tavaliselt, mis on kõige kiirem. Siin tuli mängu "Suur O".

Big O tähis, mida mõnikord nimetatakse ka asümptootiliseks analüüsiks, vaatleb peamiselt seda, kui palju toiminguid võtab sortimisalgoritm väga suure andmekogumi täielikuks sorteerimiseks. See on efektiivsuse näitaja ja see, kuidas saate ühte algoritmi otse teisega võrrelda.

Ehitades lihtsat rakendust, kus töötamiseks on ainult mõned andmed, pole selline analüüs vajalik. Kuid kui töötate väga suure hulga andmetega, näiteks sotsiaalmeedia sait või suur e-kaubanduse sait, kus on palju kliente ja tooteid, võivad väikesed erinevused algoritmide vahel olla märkimisväärsed.

Suur O tähis asetab algoritmide efektiivsuse

Ta teeb seda seoses O ja n-ga (näiteks: O (log n)) , kus

  • O viitab funktsiooni järjekorrale ehk selle kasvukiirusele ja
  • n on sorteeritava massiivi pikkus.

Vaatame läbi näite. Kui algoritmil on vajalike toimingute arv, on valem:

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

Kui “ n ” läheneb lõpmatusele (väga suurte andmekogumite puhul), on kolmest olemasolevast terminist ainus oluline 6n ^ 4 . Nii et väiksemad mõisted 2n ^ 3 ja 5 jäetakse tegelikult lihtsalt välja, kuna need on tähtsusetud. Sama kehtib 6n ^ 4-s oleva “ 6 ” kohta .

Seetõttu oleks selle funktsiooni järjestuste kasvumäär ehk „suure O” reiting O (n ^ 4).

Vaadates paljusid kõige sagedamini kasutatavaid sortimisalgoritme,O (n log n) hinnang üldiselt on parim, mida on võimalik saavutada. Selle reitinguga töötavad algoritmid hõlmavad kiiret sorteerimist, kuhjaga sorteerimist ja ühendamise sortimist. Kiire sortimine on standard ja seda kasutatakse vaikimisi peaaegu kõigis tarkvarakeeltes.

Oluline on märkida, et pole ühte algoritmi, mis oleks kõigil juhtudel kõige kiirem , kuna andmeid saab programmi sisestada kõigis osariikide viisides. Ja iga algoritmi lähenemisviisidel on parim ja halvim stsenaarium, kus need toimivad parimal või halvimal juhul.

Kuigi kiirsortimine on standard, konkureerib see ka Merge Sort ja Heap Sort, mis on muud O (n log n) hinnatud sortimisalgoritmid. On stsenaariume, kus neid kasutatakse hoopis.

Kiire sorteerimise otsene konkurent on Heap Sort. Heap Sordi jooksuaeg on samuti O (n log n), kuid Heap Sorti keskmist jooksuaega peetakse tavaliselt aeglasemaks kui omas kohas Quick Sort.

Ühenda sortimine on stabiilne sort , mis tähendab, et see säilitab väljundis võrdsete elementide sisestusjärjestuse, erinevalt tavalistest kohastest kiirsorteerimisest ja kuhjasortimisest.

Mullide / sisestuste / valikute sorteerimine jookseb O-l (n²) , mis võib operatsioonide arvu poolest tõeliselt suurte andmetega tegelemisel võtta palju kauem aega kui eespool loetletud, mille väärtus on O (n log n). Kuid võib olla ka stsenaariume, kus teised sõltuvad andmetest kiiremini.

On ka olukordi, kus midagi väga lihtsat, näiteks sorteerimise loendamine, on suurepärane, sest see on palju kiirem üles kirjutada ning palju lihtsam visualiseerida ja mõista.

Mõnikord peate arvestama mitte ainult algoritmi ajavajadustega, vaid ka andmeruumi nõudmistega (või võib-olla isegi rohkem). Mõni algoritm töötab ka väiksema jalajäljega.

Miks peate seda kõike teadma?

Nii et pärast kõike seda, kui kasutate alati ainult keele sisseehitatud sorteerimisalgoritmi (mis põhineb kiirel sortimisel), siis miks peaks hoolitsema algoritmide sorteerimise ja "Big O" eest? Miks peaksid ettevõtted selle kohta intervjuus küsima?

Vastus on, et Big O-nootide uurimine aitab teil oma koodis mõista väga olulist tõhususe mõistet. Nii et kui töötate tohutute andmekogumitega, saate hästi aru, kus suurem aeglustumine võib tõenäoliselt põhjustada kitsaskohti ja kuhu tuleks suurimate parenduste saamiseks rohkem tähelepanu pöörata. Seda nimetatakse ka tundlikkusanalüüsiks ning see on oluline osa probleemide lahendamisel ja suurepärase tarkvara kirjutamisel.

Nii et kui proovite valmistuda oma esimeseks intervjuuks või ehk nägi vaeva viimases, aitab teadmiste suurendamine selliste mõistete kohta nagu Big O Notation ja muud infotehnoloogia teemad aidata teil jalga üles tõsta. Teil on parem varustus oma potentsiaali demonstreerimiseks ja mulje saamiseks selle positsiooni saavutamiseks.