Herleitung explizite Formel und Rekursionsformel

[SomeProb]

Hallo,

ich habe auf meinen Üblatt folgenden Programmtext gegeben:

// 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;
}

Für die Rekursionsformel habe ich mir gedacht:
T(n)=2*T(n/2)+O(n)

Das Array wird ja in zwei Hälften geteilt, daher 2*T(n/2). Die For-Schleifen müssen durchlaufen werden, was n^2 ergibt. In O-Notation als O(n).

Für die explizite Formel hätte ich dann weiter abgeschätzt:
T(n)<=2*T(n/2)+O(n)<=...<=O...
Aber irgendwie beschleicht mich das Gefühl, dass meine Rekursionsformel falsch ist, weswegen ich die explizite Formel noch nicht abgleitet habe und hier um Hilfe such.

 

[Fant]

n^2 ist nicht in O(n)

Aber was willst du denn nun überhaupt machen? Wieso interessiert dich die Laufzeit, wenn du eine iterative Lösung zu deinem Problem suchst?

 

[SomeProb]

Ich möchte eine Rekursionsformel für die Laufzeit des Algorithmus angeben in Abhängigkeit von der Länge n des Arrays.

 

[Fant]

Dann sind deine Überlegungen in Ordnung. Nur eben, dass n^2 natürlich nicht in O(n) liegt...

Gruß Fant

 

[SomeProb]

n^2 ist in O(n^2), nehme ich an?

Die angegebene Rekursionsformel bezieht sich dann auf den Fall, dass n>1 ist. Wenn das Array nur aus einem Element besteht, dann gilt O(1).

Für die explizite Formel:
T(n)<=2*T(n/2)+O(n^2)<=4*T(n/4)+3O(n^2)<=8T(n/16)+7O(n^2)<=...<=2^i*T(n/2*2^i)+2^i-1*O(n^2)
Problem: Bisher wurde immer angenommen, dass n=2^k gilt. Das kann man ja nun für das Array nicht annehmen.

 

[Fant]

Natürlich ist n^2 (unter anderem) in O(n^2). Ist dir die Notation überhaupt klar?

Zunächst den Fall, dass n sich als 2^k für geeignetes k schreiben lässt, ist genau das, as du auch hier machen solltest. Wenn du sagst, dass man das hier ja nicht einfach so darf, dann hast du bei euren vorherigen Beispielen vermutlich auch nicht verstanden, wieso man das dort gemacht hat? Dann würd ich dir raten, dir das an einem schon fertig gerechneten Beispiel noch mal wirklich klar zu machen.

Und: Du schreibst nicht das auf, was du vermutlich meinst. Klammern wirken Wunder!

 

[SomeProb]

Also bei der Herleitung der expliziten Formel habe ich einen Fehler gemacht:
T(n)=2*T(n/2)+O(n^2)
<=2*(T(n/4)+O(n^2))+O(n^2)
<=4*T(n/4)+3O(n^2)
<=8*T(n/4)+7O(n^2)
...
<=2^iT(n/2^i)+2^i-1*O(n^2)

Die O-Notation habe ich vom Prinzip schon verstanden.

Warum man diese vereinfachende Annahme macht, ist mir allerdings nicht ganz klar. Wenn n nicht durch 2 teilbar wäre (also n!=2^k), dann würden ungerade Zahlen herauskommen, wenn man durch 2 teilt.

 

[SomeProb]

Ich mache jetzt einfach mal weiter:

<=2^iT(n/2^i)+2^i-1*O(n^2)
<=n*T(1)+n*O(n^2)
<=n*O(n)+n*O(n^2)
<=O(n)+O(n^2)

Ist es evtl. der schlechteste Fall, wenn n=2^i ist. Bzw. wenn man diese Annahme nicht trifft, dann wäre die Laufzeit geringer. Also schätzt man mit n=2^i einfach die Laufzeit nach unten ab?

 

[SomeProb]

Ich wollte noch einmal nachfragen: Stimmt das so?

 

[Sesostris]

Du hast nicht wirklich das gemacht, was du im Titel des Threads angegeben hast: eine explizite bzw. rekursive Formel für deinen Pseudocode sieht anders aus. Für die rekursive Formel bekomme ich T(n) = 2*T(n/2)+n^2/4 mit T(1)=1 und für die explizite T(n) = n*(n+1)/2, sofern ich mich nicht in der Eile verschaut habe. Aus der letzteren ist dann ersichtlich, dass die Problemstellung nicht nur in O(n^2), sondern auch in Theta(n^2) liegt. Was sich übrigens auch mittels Master Theorem aus der rekursiven Formel schließen lässt.
(Alle Angaben beziehen sich auf die Anzahl der Vergleiche im Worst Case, d. h. a ist duplikatfrei.)

 

[SomeProb]

Na ja, so ist die Aufgabenstellung:
Geben Sie eine Rekursionsformel für die Laufzeit des Algorithmus in Abhängigkeit von der
Länge n des Arrays an und leiten Sie daraus die explizite Formel in O-Notation her.

Also meine Rekursionsformel lautete T(n)=2*T(n/2)+O(n^2). n^2/4 ist doch in O(n^2), da Faktoren weggelassen werden. Aber wie kommst du auf n^2/4. n^2 ist mir noch klar, da es eine verschachtelte for-Schleife gibt. Aber warum teilst du das durch 4?

Warum bin ich jetzt von der Aufgabenstellung abgewichen? Meine Rekursionsformel sieht doch gar nicht so anders aus als deine.

 

[Roydebatzen]

lol ich bin voll der Döschi,

du teilst durch 4, weil du ein aLeft =n/2 * mal einem aRight=n/2 hast also n²/4.

 

[Fant]

du teilst durch 4, weil du ein aLeft =n/2 * mal einem aRight=n/2 hast also n²/4.

Genau das ist der Grund, auch wenn der Faktor 1/4 keinen weiteren Einfluss auf die Aufwandsberechnung hat.

Deine Aufwandsberechnung für T(n) ist aber leider falsch.

 

[SomeProb]

Es gilt ja T(n)=2*T(n/2)+n^2/4, falls n>1 ist.
T(n)=2*T(n/2)+n^2/4
<=4*T(n/4)+3/8*n^2
<=8*T(n/8)+7/16*n^2
=16*T(n/16)+15/32*n^2
<=...
<=2^i*T(n/2^i)+(2^i-1)/(2*2^i)*n^2

Mit k-maliger Anwendung der Rekursionsformel und n=2^k folgt:
n+(n-1)/2*n
Summanden niedriger Ordnung werden weggelassen:

(n-1)/2*n.

Stimmt es nun?

 

[Sesostris]

Mit k-maliger Anwendung der Rekursionsformel und n=2^k folgt:
n+(n-1)/2*n

Das stimmt nun, ja, und deckt sich auch mit der Formel, die ich weiter oben gepostet habe.

Aber was ist demzufolge dein Ergebnis? "(n-1)/2*n"? Das liegt in welchem O und warum?
Du musst auf n+(n-1)/2*n eigentlich nur noch die Definition von O anwenden und bist fertig.

 

[SomeProb]

Naja, ich habe es noch ausmultipliziert:
n+(n-1)/2*n=n+n^2/2-n/2. Summanden niedriger Ordnung werden weggelassen-->Damit liegt die explizite Formel in O(n^2).