Mergesort - Aufteilen bei ungerader Länge

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Mergesort - Aufteilen bei ungerader Länge

Beitrag von AnnaW »

Hallo,

ich habe kurz ein Frage zur Aufteilung der Sequenz. Wenn ich jetzt, wie in der Übung, eine Sequenz mit 9 Elementen habe, hält dann S1 4 oder 5 Elemente? Wie wird da geteilt? Auch im nächsten Schritt, wenn der Teil mit 5 Elementen geteilt wird, hab ich dann 2 - 3 oder 3 - 2 Elemente? Ich kann dazu leider nichts finden.

Viele Grüße

Anna

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

Re: Mergesort - Aufteilen bei ungerader Länge

Beitrag von JannikV »

Hey, du kannst dir aussuchen ob du immer die linke oder immer die rechte Seite größer sein lassen willst.
Im Wiki steht ja nur: The sequence is divided into two subsequences of approximately half size, it does not matter at all in which way this is done.

VG

AnnaW
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 29. Jul 2012 23:05

Re: Mergesort - Aufteilen bei ungerader Länge

Beitrag von AnnaW »

Danke für die Antwort :-)

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

Re: Mergesort - Aufteilen bei ungerader Länge

Beitrag von Malte »

Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante Bild und Bild.

Ist das richtig, dass beide Terme in Gaußen Abrundungsklammern stehen? Wenn beide Teile einer ungeraden Sequenz halbiert und abgerundet werden, dürfte dabei doch ein Element verloren gehen.


Im Beweis steht dann das hier:
"So, the lengths of s1' and s2' are at most Bild of the length of s'. Consequently, the lengths of s1' and s2' are at least Bild of the length of s'"

heißt s1' und s2' haben höchstens die abgerundete halbierte, aber gleichzeitig mindestens die aufgerundete halbierte Länge von s'? Also im Beispiel von s' mit Länge 9 hätten s1' und s2' höchstens Länge 4 und mindestens Länge 5?

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Re: Mergesort - Aufteilen bei ungerader Länge

Beitrag von jw. »

Malte hat geschrieben:Ahja, genau dazu hab ich auch nochmal eine Frage.
Im Wiki steht unter Abstract view in der Variante Bild und Bild.

Ist das richtig, dass beide Terme in Gaußen Abrundungsklammern stehen? Wenn beide Teile einer ungeraden Sequenz halbiert und abgerundet werden, dürfte dabei doch ein Element verloren gehen.
Du verwechselst Auf- und Abrundungsfunktion, siehe Wikipedia:
http://de.wikipedia.org/wiki/Abrundungs ... gsfunktion

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

Re: Mergesort - Aufteilen bei ungerader Länge

Beitrag von Malte »

Okay, dann lag da mein Fehler, hab es mir wohl falsch rum gemerkt :-)
Danke vielmals, dann habe ich nichts gesagt ;-)

Antworten

Zurück zu „Archiv“