Cuprins:
Definiție - Ce înseamnă complexitatea timpului?
Complexitatea timpului este un concept în informatică care se ocupă de cuantificarea duratei de timp luate de un set de coduri sau algoritm pentru a procesa sau rula ca funcție a cantității de intrare.
Cu alte cuvinte, complexitatea timpului este în esență eficiența, sau cât durează o funcție de program pentru a procesa o intrare dată.
Techopedia explică complexitatea timpului
Complexitatea timpului este pur și simplu o măsură a timpului necesar pentru o funcție sau expresie pentru a-și finaliza sarcina, precum și numele procesului pentru a măsura timpul. Poate fi aplicat la aproape orice algoritm sau funcție, dar este mai util pentru funcțiile recursive. Nu prea are rost să măsurăm complexitatea timpului pentru aplicații precum preluarea numelui de utilizator și a parolei dintr-o bază de date pentru comparație sau pur și simplu salvarea datelor, indiferent dacă este de 20 ms sau 5 ms; asta ar fi mai mult în linia timpului de acces. Nu are nimic de-a face cu grija timpului său de execuție, ci mai degrabă că diferența este neglijabilă. Cu toate acestea, dacă există o funcție recursivă care poate fi numită de mai multe ori, determinarea și înțelegerea sursei complexității sale de timp poate contribui la scurtarea timpului total de procesare de la, de exemplu, la 600 ms la 100 ms.
Complexitatea timpului este exprimată în mod tipic în „nota mare O”, dar există și alte notații. Aceasta este o reprezentare matematică a limitei superioare a factorului de scalare pentru un algoritm și este scrisă ca O (Nn), „N” fiind numărul de intrări și „n” fiind numărul de expresii în buclă. De exemplu, avem algoritmul:
numbers = {5, 6, 10, 11, 2}; foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2) {
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
Există cinci intrări în tabloul „numerelor”, iar bucla „predica” se repetă de două ori. Prin urmare, creșterea exponențială a timpului de procesare se produce pe măsură ce numărul de intrări și numărul de bucle cresc.
