Se ho un loop all'interno di un altro ciclo, tuttavia so che il ciclo interno verrà eseguito una sola volta, questo algoritmo sarà ancora O (n ^ 2)?
For i = 1 to n do
For j = 1 to i do
If (i==j) do
For k = 1 to n
{Do stuff}
Il ciclo molto interno verrà eseguito al massimo 1 volta, poiché i sarà uguale a j una sola volta per iterazione del secondo ciclo. È ancora n ^ 3?
Pensaci in questo modo. Indipendentemente da N, la funzione più interna verrà eseguita solo una volta per esecuzione del secondo ciclo. Ciò significa che la quantità di volte che viene eseguita dipende da N linearmente. Ciò significa che puoi trattare tutto all'interno del primo ciclo come un'operazione di tempo lineare (O (n)) (supponendo che {do stuff} sia anche un tempo costante). Se consideri il ciclo più esterno, vedi che fai qualcosa che richiede O (n), n volte. Ciò significa che il tempo di esecuzione complessivo è O (n ^ 2)
Se raddoppi N, ci saranno un totale di N ^ 2 iterazioni extra. Pertanto, il runtime complessivo è N ^ 2.
No, i cicli nidificati non significano automaticamente che il tuo algoritmo è O (n ^ k). L'unità di base di lavoro nell'esempio è {Do stuff} , quindi è necessario contare quante volte verrà eseguito come n . Non hai nemmeno bisogno del ciclo j , poiché conta solo da 1 a i e non fa nulla finché non raggiunge i . Solo su quella iterazione effettivamente funziona, quindi il tuo codice di esempio è O (n ^ 2).
Leggi altre domande sui tag algorithms