[infostudents] Re: Algotheorie aufgabe 1.2
- From: "Jonas Gehring" <jonas.gehring@xxxxxxxxxxxx>
- To: infostudents@xxxxxxxxxxxxx
- Date: Sun, 26 Oct 2008 22:40:28 +0100
> 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?
Das hört sich viel vernünftiger an :)
Das mit dem O(n) war nur eine schnelle Schätzung von mir, das
Sortieren hatte ich vergessen.
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:
>>> > //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:
