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

 
Aug 01, 2017 - 06:46 PM


Select language
Preferred language:


Online
There are 1 unlogged user and 0 registered users online.

You can log-in or register for a user account here.

Anmeldung




 


 Log in Problems?
 New User? Sign Up!
FAQ FAQ  •  Search Search  •  Register Register  •  Log in to check your private messages Log in to check your private messages
Log in Log in  •  Maximize Maximize

1661 SS EA 1-3 bc)
Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das... Forum Index » Informatik » Snippets
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
Author Message
rgerhardsOffline
Post subject: 1661 SS EA 1-3 bc)  PostPosted: Apr 19, 2009 - 08:41 PM



Joined: Sep 25, 2006
Posts: 688

Status: Offline
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.
 
 View user's profile Send private message  
Reply with quote Back to top
Display posts from previous:     
Jump to:  
All times are GMT + 1 Hour
Post new topic   Reply to topic
View previous topic Printable version Log in to check your private messages View next topic
 Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das... Forum Index » Informatik »  Snippets
Powered by PNphpBB2 © 2003-2007 The PNphpBB Group
Credits
:: RSS Feed: ::
Page created in 0.13375711441 seconds.
Ferientips - das Urlaubsweb - Jan Gerhards - Ulrike Gerhards - Ulrike Gerhards Foto Site