[infostudents] Re: Algo: 1.2 (Gleiche X-koordinate == O(n^2)

  • From: Gökhan Özer <ozer@xxxxxxxxxxxxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Mon, 27 Oct 2008 10:08:48 +0100

Wieso vergleiche ich die peiden Paare nicht..?
Meine "virtuelle Grenze" liegt bei 3 ( da ich bei x=3 die Menge Teile).
Dadurch das mindist=2 gilt, kommen alle möglichen Punkte für ein d_left&right in Frage..???

Oder stehe ich gerade komplett auf dem Schlauch..?

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 
    
  


-- 
Gökhan Özer
Colombistrasse 17
789098 Freiburg
Matrikel Nr.: 1302829
Tel: 0176-21969169
--- Sent through the Infostudents Mailinglist List Archive: http://www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: http://www.freelists.org/list/infostudents

Other related posts: