Wie lautet die Laufzeit des Algorithmus?
Hallo,
ich habe folgenden Code:
und würde hier gerne die Laufzeit bestimmen.
Leider weiß ich gerade nicht wie man "i/=2" bewerten soll, wird dies logarithmisch?
Ich persönlich würde somit O(N*log(N)) sagen.
5 Antworten
Angenommen n hat die Form 2^k
Dann wird im ersten schleifundurchgang n mal addiert
im 2. n/2 mal
Im dritten n/4
Und so weiter
Also ist die Gesamtzahl der aufsummierungen gleich:
Die Summe von i=0 bis k von n*1/2^i
Das n kannst du ausklammern und du erhälst nun die geometrische Reihe.
Zusammengefasst bekommst du dann den term:
n*(1-1/2^(k+1))/(1-1/2)
Bzw 2n*(1-1/2^(k+1)) < 2n
Also müsste es O(n) sein
Ja es wird durch die äußere Schleife logarithmisch. O(log(n)*log(n)) sollte die Laufzeit sein.
Die innere wird nicht log(n) mal durchlaufen, sondern viel öfter. Hab den selben Fehler gemacht.
Hi,
ich würde behaupten du hast da eine Endlosschleife. Ein beliebiger Wert n immer wieder halbiert (Teilung durch 2) nähert sich Null an, wird aber nie null. Somit bleibt i immer grösser null und die schleife bricht nicht ab
nevermind
i immer zu halbieren ist logarithmisch, ja.
In deiner Laufzeit müsste aber n und x drin vorkommen, N aber nicht.
wenn i = 1 und durch 2 geteilt wird ist das Ergebnis 0 bei Integerdivision