Die Idee hinter der Berechnung der Zeit Komplexität ist, wie viel Zeit Ihre Schleife/Funktion führt jeden Schritt darin aus?
zum Beispiel: for
Schleife
for (int i=0; i < n; i++) {
cout << "hello" << endl;
}
der Code in geschweiften Klammern werden n
mal hello
so die Zeitkomplexität dieser for-Schleife wird O(n)
for (int i=0; i < n; i++) {
cout << "hello" << endl;
}
for (int i=0; i < n; i++) {
cout << "hello" << endl;
}
dies mehr gedruckt werden hello
2 Zeit drucken als das vorherige, da es zwei for-Schleife hat. Zeitkomplexität ist O (2n). Wir ignorieren die Konstanten, während die Zeit Komplexität der Berechnung so die Komplexität der Zeit sein wird, O(n)
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
cout << "hello" << endl;
}
}
diese hello
n^2
Zeit gedruckt werden, warum? denn für jede äußere for loop (i)
führen Sie innere for loop(j)
O(n)
Zeit. so wird O(n^2)
Zeitkomplexität sein
weiter lesen http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/
die Laufzeit der ersten Schleife Angenommen, war 'n = 5' Einheiten. Wie hoch ist die Gesamtlaufzeit, 10 Einheiten ('2 * n') oder 25 Einheiten (' n^2')? –
Im Allgemeinen habe ich es immer als verschachtelte Schleifen betrachtet, die du multiplizierst und aufeinanderfolgende Schleifen hinzufügst. Konstanten fallen aus der letzten Komplexität –
'O (n * schlechteste_Runtime_of_both {......})' – lllllllllll