[infostudents] Re: Algotheorie aufgabe 1.2

  • From: Oleg <olegus@xxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Sun, 26 Oct 2008 22:41:09 +0100

Hallo,

beim Merge-Schritt muss doch eine Liste mit Punkten erstellt werden, die nach y-Koordinaten sortiert sind und im Bereich Schnittlinie-d und Schnittlinie+d liegen. Mit Hilfe dieser Liste berechnet man dann d_left&right. In dem Fall d=0 ist diese Liste leer, aber um das festzustellen geht doch der Alg. trotzdem die anfangs nach y-sortierte Liste durch und prüft ob die Punkte in dem Bereich um die Schnittlinie liegen oder nicht (Folie 23).

Dafür braucht man O(n) Schritte und nicht O(1). Somit bleibt die Laufzeit bei O(n * log n).

Liege ich da falsch?

Gruß,
Oleg


Jonas Gehring schrieb:
Hi,

meiner Meinung nach ist der Algorithmus dann schneller fertig, so in der Art wie es auch Gökhan formuliert hat. Wenn eines der d_left bzw d_right 0 ist gibt es keine Punkte mehr, die beim Mergen berücksichtigt werden müssen, da es natürlich keinen Punkt gibt, der einen Abstand kleiner als 0 von der Schnittlinie hat. Wenn meine Schätzung richig ist müsste der Aufwand dann bei O(n) liegen.

Gruß,
Jonas

On Sunday 26 October 2008 19:40:45 Benjamin Lieberwirth wrote:
Also entweder O(n^2) oder der algo hat n problem mit dem divide step?
oder macht er den dann einfach nicht? wenn ja dann ganz klar O(n^2) würd
ich imho sagen :)

mfg Ben

0x4655 schrieb:
mal ne Frage :

Was passiert wenn alle Punkte aufeinander liegen, d.h alle Punkte den
gleichen x und y Wert aufweisen. dann wird doch beim entlang laufen
der Grenze jeder Punkt mit jedem verglichen. D.h O(n^2) , oder?

mfg ivo
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

Subscribe / Unsubscribe:
http://www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

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


---
Sent through the Infostudents Mailinglist

List Archive:
http://www.freelists.org/archives/infostudents/

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

Other related posts: