[infostudents] Re: Algotheorie aufgabe 1.2

  • From: Jonas Gehring <jonas.gehring@xxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Mon, 27 Oct 2008 10:09:03 +0100

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


Other related posts: