[infostudents] Re: Algotheorie aufgabe 1.2

  • From: "Jonas Sternisko" <sternis@xxxxxxxxxxxxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Sun, 26 Oct 2008 22:04:24 +0100 (MET)

Hi,

ich denke auch, dass der Algorithmus durch triviale Merge-Schritte
schneller ein Ergebnis liefert.
Aber wie kommst du auf O(n)? Weil kein D&C mehr nötig ist, sobald man zwei
identische Punkte gefunden hat?
Die Punktmenge muss doch nach wie vor sortiert werden und dafür braucht
man O(nlogn). Oder kann man die Sortierung umgehen?

Gruß,
Jonas

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