Induktionsschritt bei Laufzeitanalyse von Mergesort

Aufrufe: 66     Aktiv: 09.09.2021 um 11:29

1

Ich verstehe nicht so ganz wie man durch Induktion auf die Gleichung 9.2 kommt. Kann mir das jemand geneuer erklären? Den Rest habe ich sonst verstanden. Vielen Dank schonmal im voraus für eure Antworten.
Edit: \( n=2^m\)
Diese Frage melden
gefragt

Punkte: 48

 

Hast du vielleicht vorher im Skript mal etwas über die Laufzeitberechnung eines Mergesorts konkret als Formel stehen?   ─   lernspass 08.09.2021 um 11:59
Kommentar schreiben
1 Antwort
1
Eine wichtige Sache hast Du uns verschwiegen (die auf der Seite davor steht): $n=2^m$.
Damit lautet (9.1) $M_{2n} = 2\,M_n+Z_{2n}$.
Die Induktion läuft dann über $m$. Dann geht der Induktionsschritt in 1-2 Zeilen pro Ungleichung, unter Benutzung von $n=2^m$, den (Un)Gleichungen im Text und der Induktionsvoraussetzung.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 16.14K

 

Vielen Dank für die Antwort. Das habe ich tatsächlich vergessen anzugeben. Ist denn jetzt (9.1) die Induktionsvoraussetzung und somit M(1)=0 der Induktionsanfang?   ─   freakbob999 09.09.2021 um 09:24

Induktion über m bedeutet hier: Ind. Anf. ist für m=0, also n=1 (Formel oben). Für den Schritt m->m+1 braucht man (9.1). Es steht alles in meiner Antwort bzw. von dort auf den Text verwiesen. Das sind alle Zutaten. Schreib Dir Ind. Ann. und Ind. Beh. sauber auf, dann klappt das schon.   ─   mikn 09.09.2021 um 09:59

Okay vielen Dank, ich werde mich gleich mal daran versuchen   ─   freakbob999 09.09.2021 um 10:20

Nur noch mal zum Verständnis:
- Die Behauptung, die zu beweisen ist ist die Ungleichung \(m \cdot 2^{m-1} \leq M_{n} \leq (m-1)2^m + 1\)
- Induktionsvoraussetzung ist \(M_{2n} = 2M_{n}+Z_{n}\)
- Induktionsanfang aus \(m=0 \) folgt \(n = 2^0 = 1 \) und dann \( M_{2} = 2M_{1} + Z_{2} \)
Oder liege ich damit falsch?
  ─   freakbob999 09.09.2021 um 11:09

Beh. stimmt, aber - ganz wichtig: "für alle m" davor. Über diese macht man Induktion. Ind. Anf.. m=0. Ind. Vor. HINSCHREIBEN. Ind. Beh. HINSCHREIBEN. Dann Ind. Schritt.
(9.1) ist natürlich nicht die Ind. Vor., steht da m=0?! Ich hab eigentlich oben alles gesagt. Schau Dir aber nochmal an einem einfachen Beispiel das Prinzip der Induktion an. Ich hab heute wenig Zeit, also nicht wundern, wenn ich für eine Weile nicht antworte. Es steht alles oben. Lies es Dir in Ruhe und genau durch.
  ─   mikn 09.09.2021 um 11:29

Kommentar schreiben