Ich habe jetzt extra über eine Woche gewartet, da ich denke, dass die Zeit für die Hausaufgabe mittlerweile abgelaufen sein sollte.
Dennoch habe ich mich im Verlaufe des Threads gefragt, wie man denn auf die Laufzeit des Algorithmus kommt, wenn man zuerst die Laufzeit der äußeren Schleife bestimmt.
Die Laufzeit der äußeren Schleife liegt ja in O(log n) (etwas genauer wohl in floor(ld(value))+1).
Ich habe die Komplexität folgendermaßen bestimmt:
Die
innere Schleife läuft i-mal durch.
i entwickelt sich wie folgt bezogen auf die äußere Schleife:
0. Durchgang: i=n
1. Durchgang: i=n*1/2
2. Durchgang: i=n*1/2*1/2
j. Durchgang: i=n*(1/2)^j
Daraus lässt sich für die ersten j Durchläufe die Reihe
aufstellen (wäre für die korrekte Aufgabenlösung mittels vollständiger Induktion zu beweisen).
Da dies eine geometrische Reihe ist, kann man den Grenzübergang wie folgt ermitteln:
Ergo liegt die Komplexität des Algorithmus in O(2n)=O(n).
Wenn man ein kleines Testprogramm schreibt, was die inneren Schleifendurchläufe zählt, dann sieht man, dass 2n tatsächlich richtig ist. Abhängig vom n liegt es teilweise auch unter 2. Je größer allerdings das n, desto besser passt die Näherung.
Um jetzt von der Komplexität der äußeren Schleife O(log n) auf O(n) zu kommen, müsste man irgendwie einen Korrekturterm bekommen (n/log n ?). Wie bekommt man den dann?