Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das...

Snippets - 1661 SS EA 1-3 bc)
rgerhards - 19.04.2009, 20:41 Uhr
Titel: 1661 SS EA 1-3 bc)
Die Kosten werden laut Aufgabenstellung durch den \emph{if $m_1 > m_2$} bestimmt. Es ist also zu ermitteln, wie oft dieser durchlaufen wird. Ist lediglich ein Element vorhanden, so wird er kein Mal durchlaufen, da die Rekursion unmittelbar mit dem allerersten \emph{if n = 1} terminiert. Ist n > 1, so werden jeweils die zwei Teile des Arrays durchlaufen. Laut Augabe handelt es sich bei n um eine Zweierpotenz, so dass immer zwei Teilarrays existieren. In jedem Durchlauf ist dabei eine Ausführung des \emph{if $m_1 > m_2$} erforderlich, sowie zusätzlich die Anzahl der Ausführungen aller weiteren Rekursionsstufen (also M(n/2)). Da beide Teilarrays durchlaufen werden, muss diese Laufzeit doppelt in die
Betrachtung einfliessen. Die Funktion M hat damit folgende Struktur:
\begin{aligned} &M(1) = 0\\ &M(n) = 2M(n/2) + 1, n > 1 \end{aligned}

Teil c
Da es sich bei $n$ laut Vorgabe um eine Zweierpotenz handelt, ist

n \in \{2^l | l \in \mathbb{N}_0\}

Somit gibt es stets ein l für das gilt n = 2^l.
Einsetzen in die Rekursion liefert (redundante Klammern zur Verdeutlichung):

\begin{aligned} M(n) &= 1 + 2M(n/2) \\ &= 1 + (2 + 4M(n/4)) \\ &= 1 + (2 + (4 + 8M(n/<img src="modules/PNphpBB2/images/smiles/icon_cool.gif" alt="Cool" border="0" />)) \\ &\cdots \\ &=2^0 + 2^1 + 2^2 + \cdots + 2^{l-1} \end{aligned}

Dies entspricht aber gerade der geschlossenen Formel
2^l - 1

Ich führe den Beweis mittels vollständiger Induktion über l.
Für n = 1 = 2^l ist l = 0.

Im Induktionsanfang gilt somit

M(1) = 0 = 1 - 1 = 2^0 - 1 = 2^l - 1

womit der Induktionsanfang bewiesen ist.

In der Induktionsannahme nehmen wir an, dass für ein l gilt

M(2^l) = 2^l - 1.

Dann gilt für l + 1:

\begin{aligned} M(2^{l+1}) &= 2M(2^{l+1}/2) + 1 \\ &= 2M(2^l) + 1\\ &\stackrel{\text{\tiny{IV}}}{=} 2(2^l - 1) + 1 \\ &= 2^{l+1} - 2 + 1 \\ &= 2^{l+1} - 1 \end{aligned}
Mit dem Prinzip der vollständigen Induktion folgt somit die Behauptung.
Alle Zeiten sind GMT + 1 Stunde
PNphpBB2 © 2003-2007