Complessità temporale

L'esecuzione di un programma richiede tempo, e sapere in anticipo quanto tempo richiede è utile per creare programmi efficienti. In programmazione, il tempo necessario per eseguire un programma si chiama complessità temporale.

 Per esempio

for(int i=0;i<5;i++{
   cout<<i<<endl;
}

Nell'esempio sopra, il ciclo viene eseguito cinque volte, quindi la complessità temporale è 5. In breve, la complessità temporale si riferisce al numero di iterazioni eseguite dal programma. Se un programma esegue un'iterazione, la complessità è uno, ma se esegue un numero arbitrario n di iterazioni, la complessità temporale è n

La complessità temporale usa la notazione O grande per illustrare la complessità e non scriviamo mai valori costanti all'interno della notazione. Per esempio, cinque iterazioni o sei iterazioni vengono entrambe indicate come O(1), mentre N iterazioni o 2N iterazioni vengono indicate come O(N). Quando analizziamo la complessità temporale di un programma, consideriamo il caso peggiore e calcoliamo quante iterazioni può eseguire.

Per questo particolare corso, dobbiamo capire l'importanza della complessità temporale e alcuni suoi tipi. Ne parleremo nella prossima lezione.

Leggi il seguente articolo per saperne di più sull'analisi della complessità temporale.

Complessità temporale