Omer Genan (genan) În informatică, analiza algoritmilor este o parte foarte importantă. Este important să se găsească cel mai eficient algoritm pentru rezolvarea unei probleme. Este posibil să existe mai mulți algoritmi pentru a rezolva o problemă, dar provocarea aici este de a-l alege pe cel mai eficient.
Acum, întrebarea este cum putem recunoaște cel mai eficient algoritm dacă avem un set de algoritmi diferiți? Aici apare conceptul de complexitate în timp și spațiu a algoritmilor. Complexitatea spațială și temporală acționează ca o scală de măsurare a algoritmilor. Comparăm algoritmii pe baza complexității spațiale (cantitatea de memorie) și a complexității temporale (numărul de operații) a acestora.
Cantitatea totală de memorie a computerului utilizată de un algoritm atunci când este executat reprezintă complexitatea spațială a algoritmului respectiv. Nu vom discuta despre complexitatea spațială în acest articol
Complexitatea de timp
Astfel, complexitatea în timp reprezintă numărul de operații pe care un algoritm le efectuează pentru a-și îndeplini sarcina (considerând că fiecare operație durează același timp). Algoritmul care îndeplinește sarcina în cel mai mic număr de operații este considerat cel mai eficient din punct de vedere al complexității timpului. Cu toate acestea, complexitatea spațială și cea temporală sunt afectate și de factori precum sistemul de operare și hardware-ul, dar nu îi includem în această discuție.
Acum, pentru a înțelege complexitatea timpului, vom lua un exemplu în care vom compara doi algoritmi diferiți care sunt utilizați pentru a rezolva o anumită problemă.
Problema este căutarea. Trebuie să căutăm un element într-un tablou (în această problemă, vom presupune că tabloul este sortat în ordine crescătoare). Pentru a rezolva această problemă avem doi algoritmi:
*Cautare liniara
*Cautare binara
Să presupunem că tabloul conține zece elemente și că trebuie să găsim numărul zece în tablou.
const int array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const int search_digit = 10;
Algoritmul de căutare liniară va compara fiecare element al tabloului cu valoarea căutată. Dacă găsește valoarea căutată în tablou, va returna true.
Acum să numărăm numărul de operații pe care le efectuează. În acest caz, răspunsul este 10 (deoarece compară fiecare element al tabloului). Așadar, căutarea liniară utilizează zece operații pentru a găsi elementul dat (acesta este numărul maxim de operații pentru acest tablou; în cazul căutării liniare, acesta este cunoscut și ca fiind cel mai rău caz al unui algoritm).
În general, căutarea liniară va necesita un număr n de operații în cel mai rău caz (unde n este dimensiunea tabloului).
Să examinăm algoritmul de căutare binară pentru acest caz.
Căutarea binară poate fi ușor de înțeles prin acest exemplu
Dacă încercăm să aplicăm această logică la problema noastră, atunci, mai întâi vom compara valoarea căutată cu elementul din mijloc al tabloului, adică 5. Acum, deoarece 5 este mai mic decât 10, vom începe să căutăm valoarea căutată în elementele tabloului mai mari decât 5, în același mod până când vom obține elementul dorit 10.
Acum, încercați să numărați numărul de operații de care a avut nevoie căutarea binară pentru a găsi elementul dorit. A fost nevoie de aproximativ patru operații. Acesta a fost cel mai rău caz pentru căutarea binară. Acest lucru arată că există o relație logaritmică între numărul de operații efectuate și dimensiunea totală a matricei.
numărul de operații = log(10) = 4(aproximativ)
pentru baza 2
Putem generaliza acest rezultat pentru căutarea binară astfel:
Pentru o matrice de dimensiune n, numărul de operații efectuate de căutarea binară este: log(n)
Notația Big O
În afirmațiile de mai sus, am văzut că, pentru un tablou de dimensiune n, căutarea liniară va efectua n operații pentru a finaliza căutarea. Pe de altă parte, căutarea binară a efectuat un număr log(n) de operații (ambele pentru cel mai rău caz). Putem reprezenta acest lucru sub forma unui grafic (axa x: numărul de elemente, axa y: numărul de operații).
Este destul de clar din figură că rata de creștere a complexității pentru căutarea liniară este mult mai rapidă decât cea pentru căutarea binară.
Atunci când analizăm un algoritm, folosim o notație pentru a reprezenta complexitatea în timp a acestuia, iar această notație este notația Big O.
De exemplu: complexitatea timpului pentru căutarea liniară poate fi reprezentată ca fiind O(n) și O(log n) pentru căutarea binară (unde n și log(n) reprezintă numărul de operații).
Complexitatea în timp sau notațiile Big O pentru unii algoritmi populari sunt enumerate mai jos:
*Căutare binară: O(log n)
*Căutare liniară: O(n)
*Quick Sort: O(n * log n)
*Selection Sort: O(n * n)
*Vânzătorul ambulant : O(n!)
Concluzie
Știm că, pentru un număr mic de elemente (să zicem 10), diferența dintre numărul de operații efectuate de căutarea binară și căutarea liniară nu este atât de mare. Dar, în lumea reală, de cele mai multe ori, avem de-a face cu probleme care au bucăți mari de date.
De exemplu, dacă avem de căutat 4 miliarde de elemente, atunci, în cel mai rău caz, căutarea liniară va necesita 4 miliarde de operații pentru a-și îndeplini sarcina. Căutarea binară va finaliza această sarcină în doar 32 de operații. Aceasta este o diferență mare. Acum să presupunem că, dacă o operație durează 1 ms pentru finalizare, atunci căutarea binară va dura doar 32 ms, în timp ce căutarea liniară va dura 4 miliarde de ms (adică aproximativ 46 de zile). Aceasta este o diferență semnificativă.
Acesta este motivul pentru care studiul complexității timpului devine important atunci când este vorba de o cantitate atât de mare de date.
Pentru mai multe informatii puteti consulta articolele:
*https://www.freecodecamp.org/news/time-complexity-of-algorithms/
*https://www.youtube.com/watch?v=D6xkbGLQesk