[infostudents] Re: Algo: 1.2 (Gleiche X-koordinate == O(n^2)
- From: "Jonas Krisch" <J.Krisch@xxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Mon, 27 Oct 2008 10:03:55 +0100
Also beim vergleichen im Grenzbereich vergleichst du bspw. auf keinen Fall das
Punktepaar (2,2),(4,8).
Du vergleichst immer nur Punkte die den y-Abstand höchstens d haben.
Und das haben die beiden mit Sicherheit nicht.
Von daher vergleichst du nicht alle miteinander.
Die Laufzeit ist daher denk ich mal immer noch O(n logn).
Gruß
Jonas
> -------- Original-Nachricht --------
> Datum: Mon, 27 Oct 2008 09:45:37 +0100
> Von: "Gökhan Özer" <ozer@xxxxxxxxxxxxxxxxxxxxxxxxxx>
> An: infostudents@xxxxxxxxxxxxx
> Betreff: [infostudents] Algo: 1.2 (Gleiche X-koordinate == O(n^2)
>
> Hi,
>
> Fall1: Gleiche X-Koordinate ---> O(n^2)
>
> Da, angenommen folgende Punkte gegeben sind:
>
> - 2,2 und 4,2
>
> - 2,4 und 4,4
> - 2,6 und 4,6
> - 2,8 und 4,8
> Die mindist ist hier 2, aber es werden alle Punkte miteinanderverglichen.
>
> Beim Devide kommt man ja am Ende auf 4 Teilmengen mit je 2 Elementen.Da
> die
> dist aber identisch ist, wird der Beobachtungsbereich "d" auf 2gesetzt. Da
> aber alle Punkte von d genau "2" entfernt sind, werden nunalle Punkte
> miteinander verglichen. Das setzt sich so bei jedemMergeschritt fort,
> und
> man erhält am ende eine Laufzeit von O(n^2).. :(
>
> Es ist anschaulicher, wenn ihr euch die Punkte kurz aufzeichnet!
> --
> Gökhan Özer
> Colombistrasse 17
> 789098 Freiburg
> Matrikel Nr.:
> 1302829
> Tel:
>
> --- Sent through the Infostudents Mailinglist List Archive:
> //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe:
> //www.freelists.org/list/infostudents
--
GMX Download-Spiele: Preizsturz! Alle Puzzle-Spiele Deluxe über 60% billiger.
http://games.entertainment.gmx.net/de/entertainment/games/download/puzzle/index.html
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
Other related posts:
