6 svar
72 visningar
ABC-formeln 20
Postad: 27 dec 2020 Redigerad: 27 dec 2020

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?

Albiki 5320
Postad: 27 dec 2020 Redigerad: 27 dec 2020

Hej,

Det största möjliga värde som index ii kan anta är n2n^2 och för varje index ii utförs i värsta fall n2n^2 stycken additioner e=e+je=e+j.

En övre gräns för totala antalet additioner är därför ...

ABC-formeln 20
Postad: 27 dec 2020

Borde väl bli n^4? 

Laguna Online 12476
Postad: 27 dec 2020

Har du facit, eller hur vet du att O(n^4) är fel?

ABC-formeln 20
Postad: 27 dec 2020

Min lärare gav mig fel.

Laguna Online 12476
Postad: 27 dec 2020

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. 

jek7 41
Postad: 28 dec 2020

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.

Svara Avbryt
Close