Ce este un algoritm

Un algoritm, in limbajul cel mai simplu, reprezinta un set de pasi pe care tu ii aplici sa rezolvi o problema.

Daca te asteptai la ceva mai sofisticat, sper ca nu esti dezamagit.

Nu are sens sa cauti o definitie mai complicata, pentru ca in esenta tot "la un set de pasi care iti rezolva o problema" vei ajunge.

Ce este un algoritm - un exemplu din viata reala

Imagineaza-ti ca esti la hypermarket si vrei sa cumperi niste pepeni galbeni. De ce tocmai pepeni galbeni? Habar nu am, eu doar ti-am spus sa-ti imaginezi 😛.

Iti alegi produsele pe care vrei sa le cumperi, le bagi intr-o punga si te apropii de cantarul care te va ajuta sa afli cantitatea si cam cat o sa te coste cele cateva lucruri pe care le-ai ales.

Pe display-ul cantarului cauti numele produselor alese. Observi ca lista de produse de pe cantar este in ordine alfabetica.

Iti dai seama ca va fi foarte usor sa gasesti pe unde este produsul tau, pentru ca aceasta sortare iti permite sa sari peste anumite produse care nu sunt de interes.

Daca ai luat pepeni, nu te intereseaza nimic care incepe cu orice alta litera in afara de P.

Acum, sa ne imaginam ca mergi la alt hypermarket, unde repeti acelasi proces, cu o singura diferenta: cantarul nu are lista de produse in ordine alfabetica, ci fiecare produs are o pozitie asociata cu el.

Sa zicem ca iei tot pepeni galbeni cum ai luat ultima oara, dar vezi ceva diferit acum: fiecare produs are o pozitie asociata. Din pacate, nu te uiti cu atentie si nu retii de la "raft" ce pozitie e asociata cu produsul.

Cand ajungi la cantar iti dai seama ca era important acel numar de deasupra pretului. Din pacat, nu ai de ales si va trebui sa treci prin toate pozitiile disponibile, sa vezi unde se afla produsul tau.

In cele din urma gasesti produsul tau pe pozitia 20 sa zicem. Nu vreau sa imi imaginez daca era pe pozitia 42.

Hai sa tragem niste concluzii despre cele 2 experiente.

In cazul ambelor situatii ai urmat un algoritm prin care sa iti alegi produsul si sa determini care este costul si pretul lui:

1. Ai cautat locul de unde poti sa iti alegi pepenii favoriti.
2. Ai ales niste pepeni din gramada ce o aveai disponibila.
3. Te-ai dus la cantar.
4. Ai cantarit produsele.
5. Ai apasat tasta asociata cu produsele tale.
6. Ai bagat produsele in cos si ti-ai vazut de treaba.

Desigur, pasii enumerati mai sus ii poti lua si ii poti face mai verbosi, mai detaliati, daca doresti sa ai o imagine mai completa a tuturor microactiunilor pe care le-ai facut.

Ideea este ca desi poate tu niciodata nu stai sa scrii pe foaie toti pasii pe care ii urmezi cand faci lucruri banale, asta nu inseamna ca in mod natural, tu nu urmezi in mod intuitiv un algoritm pentru a face lucrurile de zi cu zi.

Eficienta unui algoritm

Desi probabil ti-ai dat seama deja de acest aspect, prin cele 2 exemple de mai sus am atins in mod indirect si subiectul eficientei unui algoritm.

Daca e sa revenim la momentul cand cautam produsul pe cantarul nostru, este evident ca faptul ca lista de produse este sortata in primul exemplu, influenteaza foarte mult cat timp ne ia sa gasim produsul.

Hai sa detaliem un pic pe fiecare situatie ce putem experimenta ca sa aprofundam un pic cat de importante sunt anumite detalii mici.

Cum se compara 2 algoritmi asemanatori

Haide sa exploram si mai mult exemplele noastre de zi cu zi si sa le intoarcem pe toate partile.

Un mare avantaj al faptului ca o lista este sortata (voi folosi de acum sortata in loc de ordonata, pentru ca este un termen de care te vei lovi des in algoritmica) este ca iti permite foarte usor sa gasesti ce ai nevoie.

De asemenea, poti sari peste elemente din lista, daca ai un criteriu de cautare care iti permite acest lucru.

In cazul nostru, este clar ca numele produsului influenteaza cautarea noastra.

Daca numele produsului ales incepea cu litera A, puteam sa terminam si mai repede cautarea noastra.

Totusi indiferent de ce alta litera am fi avut de cautat, aveam optiunea de a sari peste ce nu este in sfera noastra de cautare (interes).

Acum in situatia cantarului cu pozitii asociate, cel mai de ajutor lucru ar fi fost sa retinem pozitia de la "raft" asociata cu produsul nostru.

Dar pentru ca nu am retinut-o, a trebuit sa trecem prin fiecare pozitie, in speranta ca vom gasi repede ce avem nevoie.

Am gasit produsul pe pozitia 20. Totusi a trebuit sa trecem liniar (unul cate unul) prin fiecare pozitie.

Cel mai bun caz ar fi fost ca produsul nostru sa fie primul pe lista, dar pe toate cantarele de tipul acesta pe care le-am folosit, cred ca de obicei acolo se afla bananele. Deci daca nu iti iei banane, pregateste-te sa scanezi lista de optiuni a cantarului.

Puteam totusi sa avem si "ghinionul" ca produsul nostru sa fie ultimul din lista. Cautarea noastra ar fi putut dura mult mai mult, mai ales daca cantarul contine multe elemente in lista. Daca aveam 100 de optiuni disponibile, dar 200?

Daca vrei sa inveti mai multe despre cum se compara eficienta a 2 algoritmi care rezolva probleme similare, te sfatuiesc sa citesti mai multe despre Big O Notation - Cum sa masori eficienta unui algoritm.

Cum arata codul unui algoritm

Sper ca exemplele pe care ti le-am oferit sunt suficient de clare.

Totusi, ca sa intelegi cum putem aplica un algoritm prin intermediul unui limbaj de programare, hai sa discutam un pic despre cautarea binara, care este un algoritm destul de prietenos cu incepatorii.

Mai jos am scris algoritmul pentru cautare binara in JavaScript cu un mic "twist" si anume am inclus si de cate ori ori am incercat sa ghicim daca guess reprezinta si item-ul cautat.

function binarySearch(list = [], item) {
  if (item < 0) {
    // daca numarul nu este pozitiv, returnam rapid
    return 'not found'
  }

  let low = 0 // start
  let high = list.length - 1 // ultimul element
  let count = 0 // de unde incepem numaratoarea

  while (low <= high) {
    const mid = Math.floor((low + high) / 2) // optiunea din mijloc
    const guess = list[mid]
    count++

    if (guess === item) {
      const counter = count > 1 ? `${count} searches` : '1 search'
      // daca gasim elementul, il returnam impreuna cu numaratoarea
      return ['found', counter]
    } else if (guess > item) {
      // cautam de la dreapta la stanga
      high = mid - 1
    } else {
      // cautam de la stanga la dreapta
      low = mid + 1
    }
  }
  // nu am gasit nimic
  return 'not found'
}

// generam o lista de numere de la 0 la 100 - adica 101 numere.
const myList = Array.from(Array(101).keys())

console.log(binarySearch(myList, 99)) // ['found', '6 searches']
console.log(binarySearch(myList, 23)) // ['found', '7 searches']
console.log(binarySearch(myList, 12)) // ['found', '6 searches']
console.log(binarySearch(myList, 50)) // ['found', '1 searches']
console.log(binarySearch(myList, 9)) // ['found', '6 searches']
console.log(binarySearch(myList, -3)) // 'not found'
console.log(binarySearch(myList, 1)) // ['found', '7 searches']
console.log(binarySearch(myList, 10)) // ['found', '7 searches']
console.log(binarySearch(myList, 100)) // ['found', '7 searches']
console.log(binarySearch(myList, 200)) // 'not found'
console.log(binarySearch(myList, 2)) // ['found', '5 searches']

Ai vazut algoritmul de mai sus, numit cautare binara. Se numeste asa, pentru ca dupa fiecare incercare de a ghici elementul, injumatatesti lista de potentiale optiuni si sari o buna parte dintre cele 101 numere disponibile.