Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws09 [17.05.2019 15:03] – SpeedyGonzalezpruefungen:bachelor:aud:loesungws09 [17.05.2019 15:09] – SpeedyGonzalez
Zeile 189: Zeile 189:
   * **O(n log n)**   * **O(n log n)**
 Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!) Sollte es nicht O(n) sein? In den VL-Folien steht, dass das Aufbauen einer Halde aus einem Array der Länge n nur O(n) ist. (Beweis wurde ausgelassen, aber intuitiv deswegen, weil die obere Hälfte des Arrays keine Kinder in der Halde hat => ein großer Teil fällt schon mal weg!)
-Ja, in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm+ 
 +Ja O(n), in der Klausur wurde nach der effizientesten Möglichkeit gesucht. Diese baut den Heap in O(n) auf, wie hier unter 4.2.4 beschrieben: http://linux-related.de/index.html?/coding/sort/sort_heap.htm
  
 **c)** **c)**