Guida all'aggiornamento dell'analisi degli algoritmi

Naviga le tue risposte
1

Non ho ancora toccato la complessità dell'algoritmo da un po 'di tempo, quindi sto cercando di fare un aggiornamento.

Sto cercando di capire il numero di passaggi nel seguente ciclo. 

for(i = 0; i < n; i++){  
  //code  
  for(j = i + 1; j < n; j++){  
     //code  
  }  
}

Il ciclo interno verrà eseguito volte
Intendo t volte per ogni valore di j. Destra?

Nel peggiore dei casi tj sarà uguale a n-i. Dal momento che verrà eseguito per n- (i + 1) -1 volte.

Il mio approccio a questa analisi è corretto?

    
posta user10326 22.10.2011 - 20:42
fonte

1 risposta

4

Il codice interno verrà eseguito (n-1) * (n / 2) volte.

Guardare le prime iterazioni e le condizioni finali aiuta a dare uno schema generale

Quando i = 0, il codice interno passerà da 1 a n - (n-1 volte)
Quando i = 1, il codice interno passerà da 2 a n - (n-2 volte)
.
.
Quando i = n-2, il codice interno passerà da (n-1) a n - (n- (n-1))

So (n-1) + (n-2) + ... + (n- (n-1)) = (n-1) * (n / 2)

    
risposta data 22.10.2011 - 21:10
fonte

Leggi altre domande sui tag

Scrittura degli argomenti nei costruttori Qual è la definizione di Time on Task?