[infostudents] Algo: 1.2 laufzeit
- From: Gökhan Özer <ozer@xxxxxxxxxxxxxxxxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Mon, 27 Oct 2008 09:09:39 +0100
Hallo,
die Laufzeit eines Quicksort ist ja (n log n).
Wobei hier, das (log n) den Mergekosten entsprechen... (Laut dem
Beispiel vom Schindelhauer von der letzter Vorlesung).
Da wir bei MINDIST erstmal Sortieren müssen, stimmt das mit (n log n). ;)
Danach kann man aber den Mergeschritt auf T(1) beschränken. Da ja nur
noch das d_left und das d_right miteinander verglichen werden müssen.
Obwohl ich mir hierbei nicht ganz sicher bin, da man ja diesen Vergleich
insgesamt (log n) mal machen müsste ...???!?!?
Also setzt sich die laufzeit aus: O(n log n) Sortierung, und O(n) bzw.
O(n log n) zusammen. ===> O(n log n)
Grüße
P.S.: Meine am Freitag verschickte Lösung war auch nur ein Vorschlag,
bzw. ein Denkansatz ;)
--
Gökhan Özer
Colombistrasse 17
789098 Freiburg
Matrikel Nr.: 1302829
Tel: 0176-21969169
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
Other related posts:
- » [infostudents] Algo: 1.2 laufzeit
