Ho trovato questo ciclo annidato per calcolare la notazione Big-O.
for(i=0;i<n;i++)
for(j=0;j<i*i;j++)
for(k=0;k<j;k++)
Ho ottenuto la complessità temporale dell'algoritmo con questa equazione polinomiale. Supponiamo che C1, C2 e C3 siano costanti di tempo per ogni ciclo. Si prega di notare che il ciclo interno passa a i * i.
T(n) = C1(n) + C2(n/2)(n+1) + C3(n)(n^2)(n^2+1)/2
In base a questo, ha la complessità temporale di O(n^5) Ho ragione sull'equazione?
In questo caso specifico, puoi sostituire le variabili con i loro valori minimi e massimi per trovare il numero di passaggi per ciascun ciclo.
Il primo ciclo passa da 0 a n , il secondo ciclo passa da 0 a n*n e il ciclo interno passa da 0 a n*n . Quindi ci sono n 2 iterazioni del ciclo più interno, volte n 2 iterazioni del secondo ciclo, volte n iterazioni del ciclo esterno. Quindi il tuo tempo di esecuzione è O (n * n 2 * n 2 ) = O (n 5 ).
Si noti che potrebbe non essere sempre così semplice calcolare il tempo di esecuzione. Le funzioni chiamate all'interno dei loop, le ricorsioni, i loop che terminano presto, ecc. Contribuiranno tutti alla complessità del calcolo.
Leggi altre domande sui tag algorithms big-o algorithm-analysis