Was wäre die große O-Notation für zwei for-Schleifen, die nicht verschachtelt sind?Große O-Notation für zwei nicht verschachtelte Schleifen
Beispiel:
for(int i=0; i<n; i++){
System.out.println(i);
}
for(int j=0; j<n; j++){
System.out.println(j);
}
Linear
O(n) + O(n) = 2*O(n) = O(n)
Es spielt keine Rolle, wie viele nicht verschachtelte Schleifen Sie haben (wenn diese Zahl eine Konstante ist, und nicht, hängt nicht von n) die Komplexität wäre linear und würde auf die maximale Anzahl gleich von Iterationen in der Schleife.
Also bedeutet das, dass, wenn Sie 2 verschachtelt haben Loops 'O (n^2)' sollten Sie sie in 2 einzelne Loops aufteilen, um 'O (n)' um den Preis von etwas Speicher zu erhalten? – ACV
Es wäre O (2n), weil Sie laufen n + n = 2n Iterationen.
O (2n) ist im Wesentlichen äquivalent zu O (n), da 2 eine Konstante ist.
Technisch arbeitet dieser Algorithmus noch in O (n) Zeit.
Während die Anzahl von Iterationen erhöht sich um 2 für jede Erhöhung in n wird die Zeit, bei einer linearen Rate erhöht noch damit in O (n) Zeit.
Es wird O(n) + O(n) ==> Effektiv O(n) da wir keine konstanten Werte halten.
Mögliche Duplikate von [Plain Englisch Erklärung von Big O] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – GayashanNA