Top Algoritmi și structuri de date pe care trebuie să le cunoști cu adevărat
Dacă vreți să deveniți inginer software, dar nu știți de unde să începeți, haideți să vă scutesc de suspans: este vorba de algoritmi și structuri de date.
După ce veți înțelege esența acestor piloni ai programării, veți începe să îi vedeți peste tot. Și cu cât învățați mai mulți algoritmi și structuri de date, cu atât mai mult vă vor servi drept combustibil de avion pentru cariera dvs. de inginer software.
Pentru a începe, haideți mai întâi să facem o scufundare profundă în Search și Sort, două clase de algoritmi fără de care nu puteți trăi. Apoi, să facem o scurtă trecere în revistă a restului peisajului care include arbori, grafuri, programare dinamică și multe altele.
În linii mari, există două categorii de algoritmi de căutare pe care va trebui să le cunoașteți imediat: liniari și binari. Depth First Search (DFS) și Breadth First Search (BFS) sunt, de asemenea, super-importante, dar le vom păstra pentru secțiunea de traversare a grafurilor de mai jos.
Cercetare liniară
Agoritmii liniari și binari sunt numiți astfel pentru a descrie cât de mult timp (complexitatea timpului) va dura o căutare în funcție de dimensiunea intrării care face obiectul căutării.
De exemplu, în cazul algoritmilor de căutare liniară, dacă aveți 100 de elemente de căutat, atunci în cel mai rău caz ar fi necesar să vă uitați la fiecare element din intrare înainte de a da peste valoarea dorită. Se numește liniar pentru că timpul de căutare este exact corelat cu cantitatea de elemente din căutare (100 de elemente/intrare =100 de verificări/complexitate)
Pe scurt, liniar = simplu (nu există nimic inteligent în algoritm). De exemplu: imaginați-vă că încercați să-l găsiți pe prietenul dvs. Lin printre un șir de oameni care stau în picioare fără o anumită ordine. Știți deja cum arată Lin, așa că trebuie pur și simplu să vă uitați la fiecare persoană, una câte una, în succesiune, până când îl recunoașteți sau nu pe Lin. Asta este. Procedând astfel, urmați algoritmul de căutare liniară
Cercetare binară
Cercetarea binară își primește numele deoarece cuvântul binar înseamnă „din sau referitor la 2 lucruri”, iar algoritmul funcționează prin împărțirea datelor de intrare în două părți, până când găsește elementul care este căutat. O jumătate conține elementul căutat, iar cealaltă jumătate nu. Procesul continuă până când locul în care a fost împărțită intrarea devine elementul căutat. Căutarea binară este, practic, doar o abordare foarte disciplinată a procesului de eliminare. Este mai rapidă decât căutarea liniară, dar funcționează numai cu secvențe ordonate.
Un exemplu ar trebui să clarifice mai bine acest lucru. Să presupunem că încercați să îl găsiți pe prietenul dvs. Bin (care are 1,75 m) într-un șir de persoane care au fost ordonate după înălțime de la stânga la dreapta, de la cel mai scund la cel mai înalt. Este o coadă foarte lungă și nu ai timp să treci unul câte unul prin toată coada, comparând înălțimea fiecăruia cu cea a lui Bin. Ce puteți face?
Introduceți căutarea binară. Selectați persoana aflată chiar în mijlocul rândului și măsurați-i înălțimea. Aceasta are 1,70 m. Deci, imediat știi că această persoană, împreună cu toți cei din dreapta lor, nu este Bin. Acum că v-ați redus problema la jumătate, vă îndreptați atenția către restul rândului și alegeți din nou persoana din mijloc. Aceasta are 1,70 m. Așa că poți exclude acea persoană și pe toți cei din stânga ei, reducând din nou problema la jumătate. Și așa mai departe. După doar cinci sau șase astfel de împărțiri, îl găsești rapid pe Bin într-o fracțiune din timpul care ți-a luat să îl găsești pe Lin. Procedând astfel, ați urmat algoritmul de căutare binară.
Sortare
Ordonarea, cunoscută și sub numele de sortare, a listelor de elemente este una dintre cele mai frecvente sarcini de programare pe care le veți face în calitate de programator. Aici analizăm doi dintre cei mai utili algoritmi de sortare: MergeSort și QuickSort.
MergeSort
Să presupunem că, în loc să dați peste linia ordonată de persoane din exemplul de mai sus, trebuie să creați o linie ordonată de persoane dintr-un grup neordonat. Nu aveți prea mult timp la dispoziție, așa că vă gândiți la o strategie pentru a grăbi lucrurile.
Primul lucru pe care îl faceți este ca grupul de oameni, care sunt toți înghesuiți, să se împartă în două. Apoi puneți ca fiecare dintre cele două grupuri să se împartă din nou în două, și așa mai departe, până când aveți de-a face în întregime cu indivizi. Apoi începeți să împerecheați indivizii, iar cel mai înalt dintre cei doi din fiecare pereche să stea în dreapta celuilalt. Destul de curând, toată lumea este organizată în aceste perechi ordonate stânga-dreapta.
În continuare, începeți să unificați perechile ordonate în grupuri ordonate de patru; apoi uniți grupurile ordonate de patru în grupuri ordonate de opt; și așa mai departe. În cele din urmă, descoperiți că aveți o linie completă de oameni ordonată pe înălțime, exact ca cea pe care ați întâlnit-o mai sus. Fără să știți, ați urmat algoritmul MergeSort pentru a realiza performanța dumneavoastră.
.
QuickSort
QuickSort este un pic prea complex pentru a fi ușor de imaginat cu oamenii, așa că haideți să ne apropiem puțin de cod. Pentru început, să ne imaginăm că aveți o listă neordonată, sau un array, de opt numere pe care doriți să le ordonați.
4 2 13 6 15 12 7 9
Ați putea folosi MergeSort, dar ați auzit că QuickSort este în general mai rapid, așa că vă decideți să îl încercați. Primul dvs. pas este să alegeți un număr din listă numit pivot. Alegerea numărului pivot corect va face diferența în ceea ce privește rapiditatea cu care QuickSort-ul dvs. funcționează și există formule gata făcute care pot fi urmate pentru alegerea unor pivoți buni. Dar, deocamdată, haideți să păstrăm lucrurile simple și să alegem ultimul număr din matrice pentru numărul nostru pivot: 9.
4 2 13 6 15 12 7 9
Pentru a face următorul pas mai ușor de urmărit, vom crea un separator la începutul matricei și îl vom reprezenta cu semnul de lire sterline.
# 4 2 13 6 15 12 7 9
Mutându-ne de la stânga la dreapta prin tabloul nostru, obiectivul nostru este să punem orice număr mai mic decât pivotul (9) la stânga separatorului și orice număr mai mare (sau egal cu) pivotul la dreapta separatorului. Începem cu primul număr din matricea noastră: 4. Pentru a-l muta în stânga separatorului, pur și simplu mutăm separatorul în sus cu un element:
4 # 2 13 6 15 12 7 9
Facem același lucru cu următorul număr: 2.
4 2 # 13 6 15 12 7 9
Dar apoi ajungem la 13, care este mai mare decât numărul pivot 9 și se află deja în partea dreaptă a separatorului. Așa că îl lăsăm în pace. Apoi ajungem la 6, care trebuie să meargă în stânga separatorului. Așa că, mai întâi, îl interschimbăm cu 13 pentru a-l pune în poziție:
4 2 # 6 13 15 12 7 9
Apoi mutăm separatorul pe lângă el:
4 2 6 # 13 15 12 7 9
Următorul este 15, care este deja la dreapta separatorului, așa că îl lăsăm în pace. Apoi avem 12. Același lucru. Dar 7, ultimul nostru număr înainte de a ajunge la pivot, are nevoie de același tip de ajutor în deplasare ca și 6. Așa că îl schimbăm pe 7 cu 13 pentru a-l aduce în poziție:
4 2 6 # 7 15 12 13 9
Apoi, încă o dată, mutăm separatorul pe lângă el:
4 2 6 7 # 15 12 13 9
În cele din urmă, ajungem la numărul nostru pivot: 9. Urmând aceeași logică de mai sus, schimbăm 15 cu 9 pentru a obține numărul pivot acolo unde trebuie să fie:
4 2 6 7 # 9 12 13 15
Din moment ce toate numerele din stânga lui 9 sunt acum mai mici decât 9, iar toate numerele din dreapta lui 9 sunt mai mari decât 9, am terminat cu primul nostru ciclu de QuickSort. În continuare, vom trata fiecare set de patru numere de o parte și de alta a separatorului ca pe o nouă matrice căreia să îi aplicăm QuickSort. Vă vom scuti de detalii, dar următoarea rundă ne va oferi patru perechi de numere pe care să aplicăm cu ușurință ultima rundă de QuickSort. Rezultatul final va fi următoarea listă ordonată, care ne-a luat mai puțin timp să o generăm decât ar fi făcut-o cu mai simplul MergeSort:
2 4 6 7 9 12 13 15
Scheat sheet algoritmi de sortare
Aceștia sunt cei mai comuni algoritmi de sortare, cu câteva recomandări pentru când să îi folosim. Interiorizați-le! Sunt folosiți peste tot!
Heap sort: Atunci când nu aveți nevoie de o sortare stabilă și vă interesează mai mult performanța în cel mai rău caz decât performanța în cazul mediu. Este garantat a fi O(N log N) și utilizează O(1) spațiu auxiliar, ceea ce înseamnă că nu veți rămâne neașteptat fără spațiu în heap sau stivă la intrări foarte mari.
Introsort: Aceasta este o sortare rapidă care trece la o sortare pe grămadă după o anumită adâncime de recursivitate pentru a ocoli cazul cel mai rău al sortării rapide O(N²). Este aproape întotdeauna mai bună decât o sortare rapidă simplă, deoarece obțineți cazul mediu al unei sortări rapide, cu performanțe garantate O(N log N). Probabil că singurul motiv pentru a utiliza o sortare de tip heap în locul acesteia este în cazul sistemelor cu constrângeri severe de memorie, unde spațiul în stivă O(log N) este practic semnificativ.
Sortare prin inserție: Atunci când N este garantat a fi mic, inclusiv ca și caz de bază al unei sortări rapide sau al unei sortări prin fuziune. Deși este O(N²), are o constantă foarte mică și este o sortare stabilă.
Sortare cu bule, sortare prin selecție: Atunci când faceți ceva rapid și murdar și, din anumite motive, nu puteți folosi pur și simplu algoritmul de sortare al bibliotecii standard. Singurul avantaj pe care acestea îl au față de sortarea prin inserție este că sunt puțin mai ușor de implementat.
Sortare rapidă: Atunci când nu aveți nevoie de o sortare stabilă și performanța în cazul mediu contează mai mult decât performanța în cel mai rău caz. O sortare rapidă este O(N log N) în medie, O(N²) în cel mai rău caz. O implementare bună utilizează O(log N) de stocare auxiliară sub formă de spațiu în stivă pentru recursivitate.
Sortare mixtă: Atunci când aveți nevoie de o sortare stabilă, O(N log N), aceasta este cam singura opțiune. Singurele sale dezavantaje sunt că utilizează un spațiu auxiliar O(N) și are o constantă puțin mai mare decât o sortare rapidă. Există câteva sortări de fuziune in situ, dar, după părerea mea, toate sunt fie instabile, fie mai puțin bune decât O(N log N). Chiar și sortările O(N log N) in place au o constantă mult mai mare decât cea a sortării fuzionate obișnuite, astfel încât sunt mai mult curiozități teoretice decât algoritmi utili.