Quale sarebbe la notazione di Big O per due per cicli non nidificati?Big O Notation per due loop non annidati
Esempio:
for(int i=0; i<n; i++){
System.out.println(i);
}
for(int j=0; j<n; j++){
System.out.println(j);
}
lineare
O(n) + O(n) = 2*O(n) = O(n)
Non importa quanti cicli non nidificati avete (se questo numero è una costante e non dipende n) la complessità sarebbe lineare e sarebbe pari al numero massimo di iterazioni nel ciclo.
Questo significa che quando si dispone di 2 nidificati loops 'O (n^2)' dovresti dividerli in 2 single loops per ottenere 'O (n)' al prezzo di qualche memoria? – ACV
Sarebbe O (2n) perché si corre n + n = 2n iterazioni.
O (2n) è essenzialmente equivalente a O (n) poiché 2 è una costante.
Tecnicamente questo algoritmo funziona ancora in tempo O (n).
Mentre il numero di iterazioni aumenta di 2 per ogni incremento n, il tempo impiegato ancora aumenta ad un tasso lineare, quindi, a O (n).
Sarà O(n) + O(n) ==> Effettivamente O(n) poiché non manteniamo valori costanti.
Possibile duplicato di [Semplice spiegazione inglese di Big O] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – GayashanNA