Complexitatea de calcul a algoritmului, de asemenea, numit complexitatea de timp este una dintre principalele caracteristici ale algoritmului, care determină costul mașinii timpului pentru punerea sa în aplicare.
complexitatea computațională a algoritmului (sau complexitatea) se numește numărul de etape efectuate de algoritmul în cel mai rău caz. Este o funcție de dimensiunea problemei reprezentate de datele de intrare. De exemplu, pentru graficul definit prin listele de incidență, dimensiunea problemei este reprezentat ca o pereche (n, m). Complexitatea algoritmului este determinat ca o funcție f, astfel încât f (n, m) este numărul de etape ale algoritmului pentru un grafic arbitrar cu n vârfuri și muchii m.
În conformitate cu pas algoritm înțeles de instrucțiuni mașină, și în această etapă definiție complexitate de calcul depinde de sistemul utilizat și metoda pentru o comandă de difuzare. Vom fi, de asemenea, interesat în continuare nu-i exact complexitatea algoritmului, calculul care este practic imposibilă, iar complexitatea asimptotică care depinde de rata de creștere etape ale algoritmului, cu o creștere infinită dimensiunea problemei. Mai mult decât atât, complexitatea computațională este definit pentru diferitele sisteme sau metode de comenzi de difuzare diferă una de cealaltă în timpurile p, unde p - constanta reala, iar rata lor de creștere este aceeași.
Pentru comparație, rata de creștere a celor două funcții, și folosim notația sau. Noi spunem că funcția este de ordinul de creștere nu mai mult. decât funcția care este desemnată și numai atunci când există C = const și N> 0 astfel încât
Noi spunem că funcția este de ordinul de creștere nu mai puțin. decât funcția care este desemnată și numai atunci când există C = const și N> 0 astfel încât
De exemplu, pentru funcția
în virtutea simbolurilor poate fi scris că fie. În general, în cazul în care - un polinom de grad k, atunci
Din definiția următoarele proprietăți: