Funktionalgleichung < Funktionalanalysis < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo!
In Informatik halte ich einen Vortrag über verschiedene Sortierverfahren. Eines ist Mergesort. Bei einer Aufwandsbetrachtung erhält man dann die Gleichungen
[mm]A(n) = A(n/2) + A(n/2) + n[/mm]
[mm]A(1) = 0[/mm].
Die Lösung ist
[mm]A(n) = n*log_{2}(n)[/mm].
Ich wollte fragen, wie man darauf kommt. Wenn es leicht geht, könnte man das im Vortrag mal für dieses eine Beispiel zeigen. Leider habe ich aber von solchen Gleichungen keine Ahnung :-(
Könnt ihr mir helfen? Meine konkreten Fragen also:
1. Geht es leicht bzw. nachvollziehbar auch für 11. Klasse zu lösen?
2. Wie löst man es?
Vielen Dank für eure Hilfe
Stefan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:04 So 06.04.2008 | | Autor: | Loddar |
Hallo Stefan!
We man die Formel $A(n) \ = \ [mm] n*\log_2(n)$ [/mm] an sich erhält, mag vielleicht etwas unbefriedigend sein ... da ermittelt man die ersten $n_$ Glieder und versucht eine entsprechende Gesetzmäßigkeit festzustellen.
Der Nachweis dieser expliziten Darstellung aus der rekursiven Darstellung wird dann mittels vollständiger Induktion geführt.
Gruß
Loddar
|
|
|
| |
|
Danke für die Antwort!
Gut, dann bau ich es lieber nicht ein.
Das wär zuviel Mathe für die armen Mathe-GKler in unserem Info-Kurs 
Stefan
|
|
|
|
