hallo,
ich bin dabei O-Notation zu lernen und muss dafür hausaufgaben abgeben. Nur blicke ich da nicht wirklich durch und in google finde ich auch nicht alle die große hilfe...ich hoffe, ihr könnt mir weiter helfen!
Welche worst-case Laufzeit in O-Notation hat der folgende Algorithmus?
Ich bin mir nicht sicher aber ich komme auf die Laufzeit: O(n²)
die obere Schleife durchläuft n/3 Iterationen, somit O(n) und die untere verschachtelte O(n²). Summiert man den Aufwand, so ergibt die Laufzeit O(n²).
ich bin dabei O-Notation zu lernen und muss dafür hausaufgaben abgeben. Nur blicke ich da nicht wirklich durch und in google finde ich auch nicht alle die große hilfe...ich hoffe, ihr könnt mir weiter helfen!
Welche worst-case Laufzeit in O-Notation hat der folgende Algorithmus?
Java:
static void makeTrue(boolean[][] a, int n) {
for (int i = 0; i < n/3; i++) {
if (i%6 == 0) continue;
else a[i][0] = true;
}
for (int i = 0; i < n/2; i++) {
for (int j = 0; j < n-i; j += i+1) {
a[i][j] = true;
}
}
}Ich bin mir nicht sicher aber ich komme auf die Laufzeit: O(n²)
die obere Schleife durchläuft n/3 Iterationen, somit O(n) und die untere verschachtelte O(n²). Summiert man den Aufwand, so ergibt die Laufzeit O(n²).
Zuletzt bearbeitet:
opcorn:
