| Autor |
Nachricht |
rgerhards
|
|
Titel: 1661 SS EA 1-3 bc)
 Verfasst am: 19.04.2009, 20:41 Uhr
|
|
Anmeldung: 25. Sep 2006
Beiträge: 688
|
|
Die Kosten werden laut Aufgabenstellung durch den  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  terminiert. Ist  , so werden jeweils die zwei Teile des Arrays durchlaufen. Laut Augabe handelt es sich bei  um eine Zweierpotenz, so dass immer zwei Teilarrays existieren. In jedem Durchlauf ist dabei eine Ausführung des erforderlich, sowie zusätzlich die Anzahl der Ausführungen aller weiteren Rekursionsstufen (also  ). Da beide Teilarrays durchlaufen werden, muss diese Laufzeit doppelt in die
Betrachtung einfliessen. Die Funktion  hat damit folgende Struktur:
Teil c
Da es sich bei $n$ laut Vorgabe um eine Zweierpotenz handelt, ist
Somit gibt es stets ein  für das gilt  .
Einsetzen in die Rekursion liefert (redundante Klammern zur Verdeutlichung):
Dies entspricht aber gerade der geschlossenen Formel
Ich führe den Beweis mittels vollständiger Induktion über .
Für  ist  .
Im Induktionsanfang gilt somit
womit der Induktionsanfang bewiesen ist.
In der Induktionsannahme nehmen wir an, dass für ein gilt
 .
Dann gilt für  :
Mit dem Prinzip der vollständigen Induktion folgt somit die Behauptung. |
|
|
| |
|
|
|
 |
|
|
|
|
FAQ
Suchen
Registrieren
Einloggen, um private Nachrichten zu lesen
Login
Forum Maximieren
::