De ce să înveți despre complexități?

Poate ai auzit de multe ori legătură dintre programatori și algoritmi. Acest lucru se întâmplă pentru că, într-adevăr, o mare parte din activitatea unui developer este aceea de a scrie cod, adică algoritmi care să rezolve diferite probleme. Astfel, iată câteva motive pentru care cunoașterea notației Big O te poate ajuta:

• Te ajută să poți scrie algoritmi eficienți din punct de vedere al memoriei folosite și al timpului de execuție
• Vei putea analiza algoritmi scriși de alte persoane, din aceleași puncte de vedere
• Această parte teoretică este abordată la interviuri tehnice la majoritatea companiilor

Ce este notația Big O? O(n)? O(1)?

Sigur în facultate ai văzut această notație și cel mai probabil nu ai înțeles-o. Țin minte că dacă vedeam scris O(1), știam că e de bine, dar nu cunoșteam exact motivul. 

Litera O este prescurtarea pentru Ordin al funcției și exemplifică viteza de creștere a unei funcții matematice. Această notație este folosită în programare pentru a clasifica durata unui algoritm în funcție de mărimea datelor pe care lucrează. 

Pentru a face o paralelă, te poți gândi la diferența dintre un salariu fix și un salariu bazat pe rezultate, cum ar fi în vânzări. Un salariu fix îți asigură un venit constant, indiferent de efortul depus, în timp ce un salariu bazat pe rezultate, îți va aduce venituri mai mari cu cât crești în experiență și investești mai mult timp sau devi mai eficient.

Notația Big O ne arată matematic cum va evolua durata algoritmului în momentul în care cresc elementele pe care rulează acesta. Cele mai multe documentații includ astfel de notații pentru mare parte din metodele publice. Un programator poate citi notația și își va da seama dacă algoritmul este scalabil sau nu.

Notația nu determină durata absolută a unui algoritm, ci doar pe cea relativă. De exemplu, dacă vezi notat O(1), asta nu înseamnă că durează o milisecundă, o secundă sau un timp foarte mic, ci arată că indiferent de mărimea datelor, algoritmul este constant și va dura la fel, chiar dacă este vorba de un singur element sau un milion. Evident, în cele mai multe cazuri durata este una foarte mică, dar vreau să ții cont că acest lucru nu este literă de lege. Spre exemplu, o funcție de criptare poate dura câteva minute indiferent de ce mesaj este criptat, algoritmul având complexitate O(1).

O(1)

    Aceasta notație arată că indiferent de numărul elementelor, algoritmul are o viteză constantă, fără să cauzeze probleme de scalabilitate. Cei mai populari algoritmi care au această complexitate sunt:

• accesarea unui element dintr-un vector sau o listă (dacă nu știi diferența dintre un vector și o listă, stai cu ochii pe noi deoarece urmează o serie de articole despre structuri de date)
• determinarea unui număr dacă este par sau impar
• determinarea existenței unei chei într-un dicționar/hashtable.

Pentru toți acești algoritmi nu contează dacă avem de a face cu milioane de elemente sau cu numere foarte mari, durata de execuție rămâne aceeași.

O(n)

    O altă notație la fel de populară este O(n) care arată că durata algoritmului crește liniar cu numărul elementelor pe care este rulat.

• parcurgerea unui vector
• ștergea tuturor elementelor dintr-o listă simplă
• căutare liniară

O(log n) – Timp logaritmic

Această notație este adesea folosită pentru algoritmi care folosesc metoda divide et impera (daca vrei un articol separat pentru divide et impera trimite-ne aici un emoji x), , împărțind o problemă în 2 părți egale, până când aceasta nu mai poate fi împărțită. Astfel, după fiecare iterație, fiecare problemă nou apărută este redusa la jumătate până când este găsită soluția.

• căutare binară
• Turnurile din Hanoi

O(n^2) 

    Aceasta notație este folosită în special pentru algoritmii de tipul brute force.

• bubble sort
• parcurgerea unei matrici
• existența a doi algoritmi de tipul O(n) într-o buclă

Mai jos ai un exemplu de algoritm ce conține o buclă de tip for, care pentru fiecare valoare a lui ‘i’ realizează o verificare (O(n)) și o operație de ștergere (O(n)).

            int n = 100;

         List<int> arr = new List<int>();

            for (int i = 0; i < n; i++)

         {

                if (AlgorithmCheck(i)) //AlgorithmCheck are complexitatea O(n)

             {

                 arr.RemoveAt(i); // RemoveAt are complexitatea O(n)

             }

         }

            // algoritmul are complexitatea O(n^2)

Algoritmii care au aceasta notație, durează mai mult și pot cauza probleme de scalabilitate. 

O(2^n)

    Adesea această notație este folosită pentru funcțiile recursive, unde durata algoritmului se dublează pentru fiecare element nou adăugat.

• ​metoda de determinare a numerelor fibonacci prin recursivitate

    public static int Fibonacci(int n)

{

        if (n <= 1)

     {

            return n;

     }

        else

     {

            return Fibonacci(n – 1) + Fibonacci(n – 2);

     }

}

Acești algoritmi pot cauza probleme de scalabilitate, deseori provocând excepții precum crearea de bucle recursive infinite (StackOverflowException) sau umplerea memoriei (OutOfMemoryException). Recursivitatea este una dintre cele mai uzuale surse de probleme, provocându-mi multe bătăi de cap de-a lungul timpului. 

Intamplare personală

Odată realizasem o aplicație desktop care găsea link-uri greșite de pe un anumit site. Aplicația prelua link-ul site-ului și căuta recursiv pentru fiecare pagină, ce link-uri conține și dacă sunt greșite. Pentru cele care nu erau greșite, căutam din nou. Pentru site-urile mici aceasta nu era o problema, dar un site ce conținea sute de mii de link-uri trebuia să aibă o limită cât de mult sa parcurgă algoritmul de recursivitate. Altfel poți ajunge la erorile pe care le-am precizat puțin mai sus.

Concluzie

Când ai ca scop reducerea timpului de execuție și ai de a face cu multe elemente, nu uita să cauți ce complexitate are un algoritm sau pur și simplu gândește-te cum se va executa acesta, astfel reduci o mulțime de probleme ulterioare.