În informatică, analiza algoritmilor este o parte foarte importantă. Este important să găsiți cel mai eficient algoritm pentru rezolvarea unei probleme. Este posibil să aveți mulți algoritmi pentru a rezolva o problemă, dar provocarea aici este să o alegeți pe cea mai eficientă.

Acum, ideea este, cum putem recunoaște cel mai eficient algoritm dacă avem un set de algoritmi diferiți? Aici apare conceptul de complexitate spațială și temporală a algoritmilor. Complexitatea spațiului și a timpului acționează ca o scară de măsurare pentru algoritmi. Comparăm algoritmii pe baza spațiului lor (cantitatea de memorie) și a complexității timpului (numărul de operații).

Cantitatea totală de memorie a computerului utilizată de un algoritm atunci când este executat este complexitatea spațială a algoritmului respectiv. Nu vom discuta despre complexitatea spațiului în acest articol (pentru a face acest articol puțin mai mic).

Complexitatea timpului

Deci, complexitatea timpului este numărul de operații pe care le efectuează un algoritm pentru a-și finaliza sarcina (având în vedere că fiecare operație necesită aceeași cantitate de timp). Algoritmul care efectuează 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, spațiul și complexitatea timpului sunt, de asemenea, afectate de factori precum sistemul de operare și hardware-ul dvs., dar nu le 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 folosiți pentru a rezolva o anumită problemă.

Problema este căutarea. Trebuie să căutăm un element într-o matrice (în această problemă, vom presupune că matricea este sortată în ordine crescătoare). Pentru a rezolva această problemă avem doi algoritmi:

1. Căutare liniară.

2. Căutare binară.

Să presupunem că matricea conține zece elemente și trebuie să găsim numărul zece din matrice.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const search_digit = 10;

Căutare liniară algoritmul va compara fiecare element al matricei cu căutare_cifră. Când găsește căutare_cifră în matrice, va reveni Adevărat.

Acum să numărăm numărul de operații pe care le efectuează. Aici, răspunsul este 10 (deoarece compară fiecare element al matricei). Deci, căutarea liniară folosește zece operații pentru a găsi elementul dat (acestea sunt numărul maxim de operații pentru această matrice; în cazul căutării liniare, aceasta este cunoscută și ca cel mai rău caz a unui algoritm).

În general, căutarea liniară va dura n numărul operațiunilor în cel mai rău caz (unde n este dimensiunea matricei).

Să examinăm Căutare binară algoritm pentru acest caz.

Căutarea binară poate fi ușor de înțeles prin acest exemplu:

O introducere in complexitatea timpului algoritmilor

Sursă: Learneroo

Dacă încercăm să aplicăm această logică asupra problemei noastre, atunci mai întâi vom compara căutare_cifră cu elementul de mijloc al matricei, adică 5. Acum, deoarece 5 este mai mic decât 10, atunci vom începe să căutăm căutare_cifră în elementele matrice mai mari de 5, în același mod până când obținem elementul dorit 10.

Acum, încercați să numărați numărul de operații efectuate de căutare binară pentru a găsi elementul dorit. A fost nevoie de aproximativ patru operații. Acum, acesta a fost cel mai rău caz pentru căutarea binară. Acest lucru arată că există un logaritmic relația dintre numărul de operații efectuate și dimensiunea totală a matricei.

număr de operații = log (10) = 4 (aprox)
pentru baza 2

Putem generaliza acest rezultat pentru căutarea binară ca:

Pentru o serie de dimensiuni n, numărul de operații efectuate de Căutarea Binară este: jurnal (n)

Notația O mare

În afirmațiile de mai sus, am văzut asta pentru o serie de dimensiuni n, se va efectua căutarea liniară n operațiuni de finalizare a căutării. Pe de altă parte, s-a efectuat căutarea binară jurnal (n) numărul de operațiuni (ambele pentru cele mai grave cazuri). Putem reprezenta acest lucru ca un grafic (axa x: numărul de elemente, axa y: numărul operațiunilor).

linearSearch%20vs%20binary%20search%20diagram 0

Sursă: Techtud

Este destul de clar din cifră că rata cu care crește complexitatea pentru căutarea liniară este mult mai rapidă decât cea pentru căutarea binară.

Când analizăm un algoritm, folosim o notație pentru a-i reprezenta complexitatea în timp și acea notație este notația Big O.

De exemplu: complexitatea timpului pentru căutarea liniară poate fi reprezentată ca Pe) și O (jurnal n) pentru căutare binară (unde, n și jurnal (n) sunt numărul de operații).

Complexitatea timpului sau notațiile Big O pentru unii algoritmi populari sunt enumerate mai jos:

  1. Căutare binară: O (jurnal n)
  2. Căutare liniară: O (n)
  3. Sortare rapidă: O (n * jurnal n)
  4. Selecție Sortare: O (n * n)
  5. Vânzător de călătorii: O (n!)

Concluzie

Apreciez foarte mult eforturile tale dacă tot citești acest articol. Acum, trebuie să vă gândiți – de ce este complexitatea timpului atât de importantă pentru a înțelege?

Știm că pentru un număr mic de elemente (să zicem 10), diferența dintre numărul de operații efectuate prin căutare binară și căutare liniară nu este atât de mare. Dar în lumea reală, de cele mai multe ori, ne confruntăm cu probleme care au mari bucăți de date.

De exemplu, dacă avem 4 miliarde de elemente de căutat, atunci, în cel mai rău caz, căutarea liniară va dura 4 miliarde de operații pentru a-și finaliza sarcina. Căutarea binară va finaliza această sarcină în doar 32 de operații. Este o mare diferență. Acum să presupunem că dacă o operațiune durează 1 ms pentru finalizare, atunci căutarea binară va dura doar 32 ms, în timp ce căutarea liniară va dura 4 miliarde ms (adică aproximativ 46 de zile). Aceasta este o diferență semnificativă.

Acesta este motivul pentru care studierea complexității timpului devine importantă atunci când vine vorba de o cantitate atât de mare de date.

Resurse

Grokking Algorithms- de Aditya Y Bhargava

Introducere în notația Big O și complexitatea timpului – de CS Dojo