Beweis Mergesort korrekt?

Benutzeravatar
ob1
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 10. Dez 2012 14:30

Beweis Mergesort korrekt?

Beitrag von ob1 »

Hi,

kleine Frage zum Komplexitätsbeweis bei Mergesort: Sind die Klammern um \(\lceil 1/2\rceil\) und \(\lfloor 1/2\rfloor\) korrekt?
Mathematisch würde ich sagen, ist das erste gleich 1, und das zweite 0. Aber das ist hier ja wohl nicht gemeint.
Ich würde sagen, entweder man nimmt das Wort "Länge" noch mit in die Klammer, oder man lässt die Klammern ganz weg.

Ist vielleicht nur eine Feinheit, aber ich bin mit diesem Klammersymbol noch nicht so vertraut, deshalb frage ich lieber mal nach. :wink:

Wie ist das eigentlich prinzipiell jetzt noch mit dem Wiki? Darf man noch Veränderungen machen, oder sollte ich damit lieber bis nach der Klausur warten?

LG, ob1

Malte
Neuling
Neuling
Beiträge: 7
Registriert: 21. Apr 2013 19:19

Re: Beweis Mergesort korrekt?

Beitrag von Malte »

Die Klammern sagen aus: "Die Längen von S1' und S2' sind höchstens die aufgerundete halbierte Länge der Sequenz S'. Also sind die Längen von S1' und S2' auch mindestens die abgerundete halbierte Länge der Sequenz S"

Die Klammern sind Notation für die Gaußsche Auf-/Abrundungsfunktion


Sollte im Wiki also stimmen. Dein Ansatz über 1 und 0 ist nicht praktikabel, da die Halbierung in jedem Rekursionsschritt angewendet wird und daher mehr als nur leer und einzelnes Element verwalten muss.

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Beweis Mergesort korrekt?

Beitrag von robertH »

Ich denke Ob1 hat hier schon Recht. Die Notation passt hier nicht ganz, auch wenn man natürlich weiß was gemeint sein soll. Die Auf- und Abrundungsklammern müssten nach S' geschlossen werden.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Beweis Mergesort korrekt?

Beitrag von JannikV »

Hi,

würde die Gaußklammer schon nach S' zugemacht und noch vor dem Halbieren, dann könnte bei ungerader Sequenzlänge eine Kommazahl rauskommen. Das ist nicht Sinn der Sache.

VG

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Beweis Mergesort korrekt?

Beitrag von robertH »

Es geht darum, dass "1/2 der Länge von S" komplett in Klammern steht und nicht nur die 1/2, die wie Ob1 richtig geschildert hat zu 1 und 0 gerundet wird.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Beweis Mergesort korrekt?

Beitrag von JannikV »

Warum denn das? Du willst doch die halbe Länge runden...

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Beweis Mergesort korrekt?

Beitrag von robertH »

Offensichtlich lesen Ob1 und ich "are at most \(\lceil 1/2\rceil\) of the length of S'" als "Einhalb aufgerundet (-->1) der Länge" und du es als "Einhalb der Länge aufgerundet". Ich sehe zwar nicht wie die Länge sich in die Rundungsklammern mogeln kann, aber von mir aus. Es sollte ja dennoch jedem klar sein, was gemeint ist.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Beweis Mergesort korrekt?

Beitrag von JannikV »

Jetzt sehe ich erst wo ihr seid. Ich habe die ganze Zeit über die Variante gesprochen und ihr über den Proof. Da habe ich nicht aufgepasst.
Ja, das ist mathematisch etwas fragwürdig.. Da habt ihr recht..

Antworten

Zurück zu „Archiv“