[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:
> > //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:
