[infostudents] Re: Algotheorie aufgabe 1.2
- From: Jonas Gehring <jonas.gehring@xxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Mon, 27 Oct 2008 12:13:35 +0100
On Sunday 26 October 2008 22:41:09 Oleg wrote:
> 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?
Stimmt, da muss ich dir rechtgeben. Mir ist entgangen, dass man natürlich
trotzdem jeden Punkt prüfen muss.
Gruß,
Jonas
> 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:
> >>> //www.freelists.org/archives/infostudents/
> >>>
> >>> Subscribe / Unsubscribe:
> >>> //www.freelists.org/list/infostudents
> >>
> >> ---
> >> Sent through the Infostudents Mailinglist
> >>
> >> List Archive:
> >> //www.freelists.org/archives/infostudents/
> >>
> >> Subscribe / Unsubscribe:
> >> //www.freelists.org/list/infostudents
>
> ---
> Sent through the Infostudents Mailinglist
>
> List Archive:
> //www.freelists.org/archives/infostudents/
>
> Subscribe / Unsubscribe:
> //www.freelists.org/list/infostudents
---
Sent through the Infostudents Mailinglist
List Archive:
//www.freelists.org/archives/infostudents/
Subscribe / Unsubscribe:
//www.freelists.org/list/infostudents
Other related posts:
