Komplexitet
Hej, jag ska bestämma en "tight O-estimation, as a function of n, of the worst case time complexity of the following loop".
Tänker väl att den bör bli O(n^4) då de två for-looparna bör köra n^2 gånger vardera, detta är dock fel. Någon som vet hur jag tänker fel?
Hej,
Det största möjliga värde som index kan anta är och för varje index utförs i värsta fall stycken additioner .
En övre gräns för totala antalet additioner är därför ...
Borde väl bli n^4?
Har du facit, eller hur vet du att O(n^4) är fel?
Min lärare gav mig fel.
Att den inre och yttre loopen körs n^2 gånger vardera stämmer inte. Det är också lite för kortfattat uttryckt, tycker jag. Det kanske är därför du fick fel. Gav uppgiften bara en poäng?
Men själva svaret är rätt.
Nu är jag inte insatt i hur man normalt anger komplexitet, men yttre loopen kör ju alltid n^2 gånger, men den inre loopen kör bara en runda/addering under första steget i yttre loopen (1 to 1), 2 rundor andra gången, 3 den tredje etc upp till n^2 den n^2:e/sista gången. Antalet adderingar är således "summan av x första talen" (där x=n^2), vilket man beräknar med x*(x+1)/2. Så stoppar man in x=n^2 där blir det väl (n^4 + n^2)/2 adderingar.
