Hi,
Ich soll für folgenden Algorithmus die Laufzeit der Rekursionsformel bestimmen:
Das Array soll die Länge n haben.
Ich hab leider keine Ahnung was die Logik dahinter ist,
aber ich würde sagen, dass die zweite If-Anweisung die Laufzeit 2*T(n/2) hat, falls n > 1.
und für die For-Schleife hört es schon auf.
Ich denke sie wird ja für je n/2 aufgerufen, also n/2*n/2 und dann halt mal dem Faktor der unterschiedlich ist. Also ist es doch T(n²/4) oder nicht?
Daraus würde dann folgen: T(n)=2*T(n/2)+T(n²/4)
Ist das richtig?
Ich soll für folgenden Algorithmus die Laufzeit der Rekursionsformel bestimmen:
Code:
// Rueckgabewert true = Duplikat-frei
boolean checkDups(a) {
if (a enthaelt nur ein Element) {
return true;
}
aLeft = linke Haelfte von a;
aRight = rechte Haelfte von a;
if (!checkDups(aLeft) || !checkDups(aRight)) {
return false;
}
for (x in aLeft) {
for (y in aRight) {
if (x == y) {
return false;
}
}
}
return true;
}
Das Array soll die Länge n haben.
Ich hab leider keine Ahnung was die Logik dahinter ist,
aber ich würde sagen, dass die zweite If-Anweisung die Laufzeit 2*T(n/2) hat, falls n > 1.
und für die For-Schleife hört es schon auf.
Ich denke sie wird ja für je n/2 aufgerufen, also n/2*n/2 und dann halt mal dem Faktor der unterschiedlich ist. Also ist es doch T(n²/4) oder nicht?
Daraus würde dann folgen: T(n)=2*T(n/2)+T(n²/4)
Ist das richtig?