[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: 
> http://www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: 
> http://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:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents

Other related posts: