Verständnisfrage Rekursionsbeispiel |
| 10.07.2015, 02:34 | -asdfg- | Auf diesen Beitrag antworten » | ||||||||
| Verständnisfrage Rekursionsbeispiel Wie wandelt man das kcn in der vorletzten Zeile in den Ausdruck cn log n um? Zugegeben, meine Mathe-Kentnisse (Logarithmusgesetze etc.) müsst sich mal verbessern. Und könnte man das a bei na nicht weglassen, oder ist dieser konstante Wert ein Wert der übergeben wird falls n=1 ist (und nicht etwa selbst zu 1 wird). 2. Warum heißt es beim 2. Blatt ((k-1). Schritt) und nicht k. Schritt und wieso ist in diesem Schritt das 2^k-1 nicht ein normales 2^k sowie das 3x2^k-2 und nicht ^k-1? Und wenn's geht noch kurz erklären wie man von der Summenformel auf (2^k-1 - 1) kommt. Will hier nicht wie so'n Amateur rüberkommen, aber mir mangelt's schon teilweise an Grundkenntnissen die ich auffrischen muss. Deshalb bedanke ich mich umso mehr für Antworten. Meine Ideen: Keine, da ich versuche die Lösung nachzuvollziehen. |
||||||||||
| 10.07.2015, 09:12 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
RE: Verständnisfrage Rekursionsbeispiel
Genau so ist es.
Weil später noch einmal mit 2 multipliziert wird und damit entsteht. Das kann dann elegant wieder in n umbenannt werden.
Das ist, wie da ja auch steht, eine geometrische Summe. Die Herleitung der Formel steht zum Beispiel hier. Viele Grüße Steffen |
||||||||||
| 10.07.2015, 10:49 | -asdfg- | Auf diesen Beitrag antworten » | ||||||||
Ahso, das macht Sinn. Wenn n = 2^k ist und sich das umwandeln lässt zu log2(n), warum kann man dann statt cn log n nicht schreiben c * 2 log n, wodurch der asymptotische Aufwand O(log n) und nicht O(n log n) ist? Welchen Logikfehler mach ich da? |
||||||||||
| 10.07.2015, 11:09 | -asdfg- | Auf diesen Beitrag antworten » | ||||||||
Ah ne, das geht nicht, weil log n = k ist und das nur aufgehen würde, wenn die Gleichung k^2*c heißen würde. Liege ich richtig? 
|
||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
