Complessità del tempo quando la variabile del ciclo dipende dalla variabile del ciclo esterno

Question

Complessità del tempo quando la variabile del ciclo dipende dalla variabile del ciclo esterno

#1 da (1 voti)

2

Qual è la complessità temporale del seguente pezzo di codice nel peggiore dei casi?

s = 0;
for( i = 1; i <= n; ++i ) {
    for( j = 1; j <= i * i; j++ ) {
        for( k = 1; k <= j and j % i == 0; k++ )
            s++;
    }
}

Ogni loop dipende dalla variabile del loop esterno. Come dovrei procedere in questo caso?

Il ciclo più interno verrà eseguito solo occasionalmente, quindi come posso valutare questo caso?

Per ogni incremento di i ciclo intermedio viene eseguito i^2 volte. Per ogni iterazione del ciclo intermedio, non sono in grado di calcolare quante volte verrà eseguito il ciclo più interno in termini di ciclo esterno.

Penso che il ciclo interno iterazioni per i volte. Il ciclo intermedio viene eseguito per j = 1 to i^2 e j % i != 0 è in i casi e per altri casi i , j % i = 0 . Poiché il ciclo interno viene eseguito per j % i == 0 , verrà ripetuto i volte.

Ora per i tempi il ciclo più interno esegue i volte, il ciclo medio esegue i^2 volte e il ciclo esterno esegue i volte, penso che la complessità sia n^4 .

complexity big-o

posta Ashish Pani 26.10.2015 - 19:03

fonte

1 risposta

Leggi altre domande sui tag complexity big-o

Come fa il runtime Python a sapere a quale oggetto è associato un metodo? Domanda di progettazione modello-vista-controller (uno contro più modelli per vista multipla + controller)

score 1 · Accepted Answer

Mentre il risultato finale è corretto, non accetterei ciò che è scritto nella domanda come risposta, perché non riesco davvero a vedere come arriva alla risposta.

Il ciclo più interno: ci sono due casi. Se j% i ≠ 0 allora itera una volta, se j% i = 0 allora itera j times.

Il ciclo medio: dato i, itera i ^ 2 volte. Il valore di j varia da 1 a i ^ 2. Ci sono i casi j = i, j = 2i, j = 3i, ..., j = i ^ 2 dove j% i = 0 e i ^ 2 - i casi in cui j% i ≠ 0. Il ciclo interno iterare una volta (i ^ 2 - i) volte. Il ciclo interno eseguirà iterazioni j volte quando j = i, j = 2i, j = 3i, ..., j = i ^ 2. Il numero totale di iterazioni è la somma di (t * i) per 1 ≤ t ≤ i, che è i * (i - 1) / 2 * i che è circa i ^ 3 / 2. Gli altri casi riguardano solo i ^ 2 - i operazioni e può quindi essere ignorato. Riepilogo: Dato i, il ciclo intermedio esegue circa le operazioni i ^ 3/2.

Il ciclo esterno: i va da 1 a n. Ci sono i ^ 3/2 operazioni per ogni iterazione. Quindi il numero totale di operazioni è la somma di (i ^ 3/2) per i = 1 a n, che è circa i ^ 4 / 8.