Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Complexitatea unui algoritm (timp și spațiu) în C++

De multe ori, pentru aceeași problemă, se găsesc metode diferite de rezolvare — mai exact, avem algoritmi diferiți. În funcție de cât de multe resurse se folosesc pentru rularea unui algoritm (în timp și în spațiu), se determină complexitatea algoritmului și mai apoi eficiența sa.

Ce reprezintă complexitatea unui algoritm?

Complexitatea unui algoritm reprezintă un mod de a măsura eficiența unui algoritm, în funcție de cât de multe resurse consumă acesta din punct de vedere al memoriei și al timpului.

Deși cu seturi mici de date eficiența unui algoritm este probabil neglijabilă, cunoașterea complexității unui algoritm este necesară în momentul în care ai o cantitate mai largă de date, iar metode mai ineficiente nu sunt folosibile.

Exemplu: complexitatea aflării numărului de divizori

Să luăm doi algoritmi diferiți care calculează numărul de divizori al unui număr n. Prima metodă ia toate numerele de la 1 la n și verifică pentru fiecare dacă este sau nu divizor al lui n, pe când a doua metodă ia doar numerele de la 1 la radicalul lui n, folosind o metodă mai eficientă (despre care poți citi în acest articol).

Prima metodă (ineficientă)

Codul arată astfel:

int nrdiv = 0;
for(int d = 1; d <= n; d++) {
    if(n % d == 0) {
        nrdiv++;
    }
}
cout << n << " are " << nrdiv << " divizori";

A doua metodă (eficientă)

Codul eficient arată astfel:

int nrdiv = 0;
for(int d = 1; d * d <= n; d++) {
    if(n % d == 0) {
        nrdiv++;
        if(d != n / d)
            nrdiv++;
    }
}
cout << n << " are " << nrdiv << " divizori";

Comparație

Se observă faptul că prima metodă merge de la 1 la n, astfel făcând n operații în total. Pe de altă parte, a doua metodă merge de la 1 până la radicalul lui n, astfel executând un maxim de sqrt(n) operații. Cum sqrt(n) ≤ n, al doilea algoritm va face, de regulă, mai puțini pași decât primul, astfel că îl considerăm mai eficient.

Acesta a fost un exemplu de complexitate a timpului, unde am numărat câți pași se efectuează în total pentru cei doi algoritmi. Similar se poate calcula și complexitatea de memorie, care vede cât de multă memorie se consumă.

Cum se calculează complexitatea unui algoritm

Complexitatea unui algoritm se calculează în funcție de câte operații se execută în program. Deoarece ne interesează strict complexitatea algoritmului, operațiile de citire și de afișare nu se iau de obicei în calcul — chiar dacă, pentru un vector, se citesc n numere, nu vom lua în considerare acest lucru.

Pentru restul operațiilor (precum comparații sau atribuiri), vom estima de câte ori apar acestea când se execută codul. Pentru exemplul de mai sus, prima metodă verifică pentru n numere (de la 1 la n), câte dintre ele sunt divizori. Astfel, vom estima că se execută n operații. Pentru a doua metodă, deoarece structura repetitivă parcurge numerele de la 1 la sqrt(n), atunci vom spune că acesta execută sqrt(n) operații.

De menționat este faptul că dacă se execută de mai multe ori n operații — de pildă, dacă avem două for-uri separate care merg de la 1 la n, deci în total 2 * n operații — atunci vom rotunji numărul total de operații la n.

Notația complexității cu Big O Notation

Complexitatea unui algoritm se notează cu O(…), unde reprezintă numărul de operații calculat mai sus. Spre exemplu, pentru primul algoritm din exemplul de mai sus, spunem că are complexitatea O(n).

Notația cu O(…) — numită Big O Notation — se referă la cel mai defavorabil caz din algoritm. Spre exemplu, dacă am avea următoarea structură repetitivă care se oprește atunci când găsește un divizor:

for(int i = 2; i <= n; i++) {
    if(n % i == 0)
        break;
}

Chiar dacă există cazuri în care codul se oprește instant (n = 2, spre exemplu) sau foarte rapid (n = 3), vom lua cel mai rău caz posibil, atunci când n este un număr prim — astfel că vom nota complexitatea algoritmului cu O(n).

Diferența dintre complexitățile algoritmilor

În imaginea de mai jos se observă clar diferența complexităților în funcție de un anumit număr n:

Grafic cu complexitatea algoritmilor

Vom lua fiecare tip de complexitate în parte și vom discuta despre aceasta.

Complexitatea constantă — O(1)

Complexitatea O(1) (constantă) reprezintă faptul că algoritmul execută instant (dintr-o singură operație) codul. Iată niște exemple de complexități constante:

  • Adunarea a două numere: a + b;
  • Aflarea sumei 1 + 2 + 3 + … + n: aceasta se află instant cu operația n * (n + 1) / 2;
  • Aflarea parității unui număr, care se află instant cu operația n % 2.

Complexitatea logaritmică — O(log n)

Complexitatea logaritmică O(log n) sau O(log2 n) sugerează un algoritm prin care se întâmplă împărțiri repetate la 2 a numărului de elemente considerate. În acest sens, exemple relevante sunt:

  • Căutarea binară: setul inițial (1, n) se împarte repetat la 2, ajungându-se în final la un singur element;
  • Algoritmi Divide et Impera: această metodă de rezolvare este bazată pe principiul că se împarte problema în subprobleme de lungime jumătate;
  • Căutare într-un arbore binar: de la fiecare nod mergem la fiul potrivit, astfel eliminând de fiecare date aproximativ jumătate din nodurile de verificat.

Complexitatea radical — O(sqrt n)

Complexitatea radical O(sqrt(n)) sau O(sqrt n) apare în algoritmi în care setul de date se împarte în mai multe seturi. În acest sens, avem ca exemplu:

  • Operațiile cu divizorii unui număr: putem să prelucrăm divizorii unui număr parcurgând doar numerele de la 1 la sqrt(n).

Complexitatea liniară — O(n)

Pe departe cea mai întâlnită complexitate, complexitate liniară O(n) execută același număr de operații cu lungimea setului de date n. Exemple de complexități liniare se găsesc în algoritmii:

  • Parcurgerea unui vector;
  • Căutarea liniară în vector;
  • Compararea a două șiruri de caractere.

Complexitatea O(n log n)

Complexitatea O(n log n) apare în cazul metodelor eficiente de sortare, precum:

  • Merge Sort;
  • Quick Sort;
  • Heap Sort;

Complexitatea pătratică — O(n2)

Complexitatea pătratică O(n * n) sau O(n2) se folosește în cazul algoritmilor în care setul de date se parcurge de n ori. În acest sens, întâlnim următoarele exemple:

  • Parcurgerea unei matrici pătratice cu latura n;
  • Sortarea prin inserție: Insertion Sort;
  • Sortarea prin selecție: Selection Sort;

Complexitatea algebraică sau polinomială — O(nc)

Această complexitate se folosește în algoritmi ineficienți sau bruți. Complexități polinomiale pot fi O(n2), O(n3), ….

Complexitatea factorial — O(n!)

Complexități de tipul O(n!) apar în algoritmi ineficienți sau bruți. Iată câteva exemple:

  • Calcularea tuturor permutărilor unui număr folosind metoda backtracking (fără afișare);
  • Calcularea partițiilor unui număr folosind metoda backtracking (fără afișare);
  • Alți algoritmi backtracking sau bruți.

Alte complexități

În algoritmi se pot îmbina complexitățile menționate mai sus, sau pot chiar să formeze complexități noi. Spre exemplu, algoritmul de generare a permutărilor are complexitatea O(n!), iar operația de afișare a elementelor unui vector are complexitatea O(n), astfel că un algoritm care calculează permutările unei submulțimi și afișează soluțiile are complexitatea O(n! * n).

Alte resurse sau bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Interclasarea a doi vectori în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Inversarea unui vector în C++Verifică dacă o literă este mică sau mare în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleCMMMC a două numere în C++ (cel mai mic multiplu comun)Maximul și minimul a n valori în C++Aria unui triunghi folosind coordonatele acestora în C++Numărul permutărilor în C++ (formula permutărilor)Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortBordarea unei matrice în C++Interschimbarea a două variabile în C++ (3 metode)Oglinditul unui număr în C++Instrucțiunea continue (structuri repetitive)Suma 1 + 2 + 3 + ... + N în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Numărul de divizori primi ai unui număr în C++Numărul combinărilor în C++ (formula combinărilor)Cel mai frecvent element dintr-un șir în C++Funcții în C++. Ce sunt subprogrameleMatrice în C++. Declararea și parcurgerea tablourilor bidimensionaleCel mai semnificativ bit în C++CMMDC recursiv a două numere naturale în C++Distanța dintre două puncte în C++Verifică dacă un caracter este literă în C++Afișarea elementelor unui vector recursiv în C++Verifică dacă un caracter este cifră în C++Recursivitate în C++Transformarea unei litere mici în literă mare în C++Instrucțiunea while (structuri repetitive)Verificare dacă șir de caractere este palindrom în C++Aria și circumferința unui cerc în C++Citirea și afișarea matricelor în C++Suma divizorilor unui număr în C++Numărul minim de peroane pentru o gară în C++Verificare dacă un număr este palindrom în C++Transformarea unui număr din baza 10 în baza 2 în C++Numere triunghiulare. Verificarea unui număr triunghiularNumărul de apariții al unui număr într-un vector în C++Radicalul unui număr în C++ (rădăcina pătrată)Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorMaximul și minimul a două valori în C++Do while vs while în C++ - Care e diferența?Comentarii în C++Inversarea unui șir de caractere în C++Valoarea absolută (modulul) unui număr în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Verifică dacă un număr dat este o putere de 2 în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Află secolul unui an citit de la tastatură în C++Verifică dacă un număr aparține șirului Fibonacci în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleInstrucțiunea de decizie în C++: if, else, switch, caseOglinditul recursiv al unui număr în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cifra de control a unui numărVerificarea unui an bisect în C++Complexitatea unui algoritm (timp și spațiu) în C++Ce înseamnă endl în C++?Verificare număr prim în C++ (Clasa a IX-a)Șiruri de caractere în C++. Tot ce trebuie să știiAl N-lea termen dintr-o progresie geometricăRădăcina cubică a unui număr în C++ (cube root)Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Verifică dacă trei puncte sunt coliniare C++Tipul struct în C++. Ce sunt structurile de date neomogeneMaximul și minimul unui vector în C++Ce este o funcție void în C++?Verifică dacă o literă este vocală în C++Ce este o variabilă unsigned în C++?Afișarea divizorilor primi ai unui număr în C++Transformarea unei litere mari în literă mică în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Aflarea sumei primelor N sume GaussCifra maximă și minimă a unui număr în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăMaximul și minimul a trei valori în C++Transformarea unui număr din baza 2 în baza 10 în C++Al N-lea termen dintr-o progresie aritmeticăȘirul lui Fibonacci în C++Indicatorul lui Euler în C++Prima cifră a unui număr în C++Numărul de cifre ale factorialului unui numărCâte numere naturale sunt într-un interval dat? (C++)Cum să citești și să afișezi în fișiere în C++Verifică dacă un număr este par sau impar fără modulo în C++Ciurul lui Eratostene în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiCodul ASCII (tabel complet)Mediana unui șir de valori în C++Al N-lea termen Fibonacci în C++Vectorii în C++: declarare și parcurgereStructuri repetitive (while, do while, for, etc)Ce înseamnă variabilă globală și locală în C++?Cel mai puțin semnificativ bit în C++Generarea șirului Fibonacci generalizat în C++Citește un șir de caractere cu spații în C++Instrucțiunea break (structuri repetitive)Copiuțe: Cifrele unui numărVectori de frecvență (de apariții) în C++Cum să afișezi partea întreagă a unui număr real în C++Matrice pătratice în C++. Diagonala principală și secundarăOperații cu numere mari în C++ - Toate funcțiile explicateCum să calculezi instant 2 la puterea N în C++Vectorii în C++: citire și afișareCifra maximă a unui număr recursiv în C++Căutare binară în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Numărul de divizori al unui număr în C++Suma numerelor naturale dintr-un interval dat în C++Cea mai lungă secvență de elemente crescătoare în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicDivide et Impera (metodă de programare C++)Instrucțiunea for (structuri repetitive)Algoritm recursiv pentru căutare binară (clasa a X-a)Instrucțiunea do while (structuri repetitive)Suma elementelor unui vector recursiv în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Calculul combinărilor de n luate câte k (nCk) în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Factorialul unui număr în C++Cel mai mic număr cu suma cifrelor N în C++Pointer în C++. Variabile de tipul char * (char steluță)

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont