Klausur 11.08.2011 - Wissensfragen

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Klausur 11.08.2011 - Wissensfragen
Hallo!

Beim Überprüfen meiner Lösungen bin auf die Lösungsversuche hier auf der FSI Seite gestoßen.

Ich würde bei Aufgabe 1c behaupten, dass die Laufzeitkomplexität O(n^2) beträgt. In obigem Lösungsversuch heißt es aber O(n).

Was meint ihr?

void foo (long n) {
    for (int i=0; i<n; i++) {
        if (i == 0) {
            doSomethinginLog(n); // O(log n)
            i++;
        }
        if (i == 1) {
            doSomethingInLinear(n); // O(n)
            i++
        }
        doSomethingO(1); // O(1)
    }
}

Wir haben eine for-Schleife mit O(n). Darin enthalten sind zwei if-Abfragen mit O(log n) und O(n) sowie ein Methodenaufruf mit O(1). Diese sollten doch addiert werden, was O(1 + log n + n) = O(n) ergibt. Und das sollte dann doch mit dem O(n) der for-Schleife multipliziert werden, also insgesamt O(n^2). Oder bin ich da völlig auf dem Holzweg?

Schonmal Danke!

3

genau das hab ich mich bei der Aufgabe auch schon gefragt…

4

Soweit ich das verstanden habe, wird ja jeweils in jede if-Abfrage nur genau 1x gegangen und zwar nacheinander.
Lediglich doSomethinInO(1) wird n-mal durch die for-Schleife ausgeführt.

Dadurch: O( log(n)) + O (n) + O (n) → max → O(n)

5

in irgendeinem anderen Thread wurde das schon diskutiert

6

oh hab übersehen, dass die schleifenklammern vorher zugehen :confused:
hab irgendwie gedacht es wär verschachtelt.

7

@Tschadiii: Vielen Dank! Das erscheint logisch.

@meisterT: Sorry, ich hatte auch schon hier im Forum gesucht, aber nichts gefunden.

Gleich die nächste Frage: Wir haben ja kennengelernt, dass HeapSort eine Komplexität von n logn hat. Inwieweit hätte man denn Aufgabe 1d beantworten können? Ich habe in den Vorlesungsfolien nichts über den Speicherplatzverbrauch von HeapSort oder anderen Sortieralgorithmen finden können.

Wie komme ich darauf, dass HeapSort “auf Reihungen mit n Elementen” mit O(1) zusätzlichem Speicherplatz auskommt?

8

Ueberleg dir mal:
In welchem Schritt braucht HeapSort wieviel zusaetzlichen Speicher?

9

Nach deinem Denkanstoß würde ich sagen: Gleich zu Beginn wird die Position des letzten Elements in ein int gespeichert, ansonsten wird nichts zusätzlich abgespeichert. Das dürfte dann für das zusätzliche O(1) verantwortlich sein?

10

Ja, zum Swap braucht man auch noch ein zusaetzliches Element. Es bleibt also bei O(1).