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
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/default/user/13_nmmslarge.png?v=1551279448000)
Ja es wird durch die äußere Schleife logarithmisch. O(log(n)*log(n)) sollte die Laufzeit sein.
![](https://images.gutefrage.net/media/user/MrAmazing2/1562539605664_nmmslarge__63_0_466_466_da6195808c107c57ce2a8b233a2bcf4f.jpg?v=1562539606000)
Die innere wird nicht log(n) mal durchlaufen, sondern viel öfter. Hab den selben Fehler gemacht.
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
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
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
![](https://images.gutefrage.net/media/default/user/13_nmmslarge.png?v=1551279448000)
nevermind
![](https://images.gutefrage.net/media/default/user/15_nmmslarge.png?v=1551279448000)
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