Algorithmus entwerfen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:36 Fr 12.06.2009 | | Autor: | Tobus |
| Aufgabe | Eingabe sind n Punkte [mm] P_{1}=(x_{1},y_{1}), [/mm] ..., [mm] P_{n}=(x_{n},y_{n}) [/mm] mit [mm] x\in [/mm] Z und [mm] y\in [/mm] {3,5,7}
Gesucht sind zwei Indizes 1<=j<k<=n, so dass der (euklidische) Abstand der Punkte minimal ist.
Der Algorithmus sollte effizienter sein, als der naive Ansatz, d.h. die Laufzeit sollte in [mm] o(n^{2}) [/mm] liegen. |
Hallo,
ich habe damit ein kleines Problem. Da die Menge der Punkte nicht geordnet ist, habe ich im Moment keine Ahnung, was mein Ansatz sein könnte.
Bitte um Hilfe ;)
DANKE
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:22 So 14.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:07 Mo 15.06.2009 | | Autor: | CSSX |
Du kannst die Punkte einmal entlang der x-Achse und einmal entlang der y-Achse in O(n*logn) Zeit ordnen. Dann bist du noch ziemlich gut in der Zeit  .
|
|
|
|
