Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursionsgleichung lösen

Rekursionsgleichung lösen

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

Michel988 aktiv_icon

12:59 Uhr, 16.12.2018

Hallo,
ich habe eine Rekursionsgleichung für Mergesorts best case aufgestellt, wenn man annimmt

n = 2^{k}, k

ist eine natürliche Zahl:

T (n) = 2 \cdot T (\frac{n}{2}) + \frac{n}{2}

Dass

O (n \cdot log (n))

eine Obergrenze ist und wie man auf diese kommt weiß ich.

Durch Einsetzen und Betrachten der Zahlen fand ich heraus, dass folgende Gleichung alle Werte exakt ermittelt:

T (n) = \frac{n \cdot log (n)}{2} = \frac{n \cdot k}{2}

Meine Frage ist, wie kann ich aus der Rekursionsgleichung oben die Gleichung unten mathematisch korrekt herleiten/beweisen?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

DerDepp aktiv_icon

15:18 Uhr, 16.12.2018

Hossa :-)

Dir fehlt noch die Abbruchbedingung für die Rekursionsgleichung. Gehen wir davon aus, dass eine Sortierung erst ab

n = 2 = 2^{1}

Elementen sinnvoll ist und die Sortierung von

2

Elementen eine konstante Zahl

c

an Operationen (Vergleiche und/oder Vertauschungen) erfordert, so ist

T (2) = c

. Die Rekursionsgleichung lautet dann also:

T (n) = 2 \cdot T (\frac{n}{2}) + \frac{n}{2}; T (2) = c; n = 2^{k}; k \in ℕ

Setzen wir ein paar Werte ein, um zu erkennen, wie sich die Rekursion entwickelt:

k = 2 : T (2^{2}) = 2 \cdot T (\frac{2^{2}}{2}) + \frac{2^{2}}{2} = 2 \cdot T (2^{1}) + 2^{1} = 2 c + 2 = 2 c + 1 \cdot 2

k = 3 : T (2^{3}) = 2 \cdot T (\frac{2^{3}}{2}) + \frac{2^{3}}{2} = 2 \cdot T (2^{2}) + 2^{2} = 2 \cdot (2 c + 2) + 4 = 4 c + 8 = 4 c + 2 \cdot 4

k = 4 : T (2^{4}) = 2 \cdot T (\frac{2^{4}}{2}) + \frac{2^{4}}{2} = 2 \cdot T (2^{3}) + 2^{3} = 2 \cdot (4 c + 8) + 8 = 8 c + 24 = 8 c + 3 \cdot 8

k = 5 : T (2^{5}) = 2 \cdot T (\frac{2^{5}}{2}) + \frac{2^{5}}{2} = 2 \cdot T (2^{4}) + 2^{4} = 2 \cdot (8 c + 24) + 16 = 16 c + 64 = 16 c + 4 \cdot 16

k = 6 : T (2^{6}) = 2 \cdot T (\frac{2^{6}}{2}) + \frac{2^{6}}{2} = 2 \cdot T (2^{5}) + 2^{5} = 2 \cdot (16 c + 64) + 32 = 32 c + 160 = 32 c + 5 \cdot 32

Daraus kann man folgende Vermutung entnehmen:

T (2^{k}) = 2^{k - 1} \cdot c + (k - 1) \cdot 2^{k - 1}

bzw.

T (n) = \frac{n}{2} \cdot c + (\log n - 1) \cdot \frac{n}{2} = \frac{n}{2} (c - 1) + \frac{n \cdot \log n}{2}

Bei der Gleichung hinter "bzw." habe ich

k = \log n

eingesetzt, um sie wieder mit

n

schreiben zu können. Das stimmt mit deiner Lösung überein, falls

c = 1

ist. Da du aber zum Sortieren von 2 Elementen immer einen Vergleich und in der Hälfte der Fälle eine Vertauschung (=3 Zuweisungen) brauchst, sollte

c = 1 + 3 / 2 = 2.5

eher realistisch sein. Dadurch bekommst du noch einen linearen Term, denn

\frac{n}{2} (c - 1) = 3 n / 4

. Nur falls bereits alle Werte sortiert sind, ist

c = 1

(nur Vergleich, keine Vertauschung) und der lineare Term entfällt.

Wenn du mathematisch exakt sein möchtest, kannst du die gefundene Formel noch durch vollständige Induktion über

k = 2, 3, 4, \dots

beweisen. Falls du dazu Hilfe benötigst, schreib einfach bitte nochmal.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1452376

1452335

	Status: nicht eingeloggt	Noch nicht registriert?