7 svar
126 visningar
exer240 behöver inte mer hjälp
exer240 25
Postad: 6 sep 2021 14:20

Datastrukturer och algoritmer

Skulle någon kunna förklara så bra den kan varför svaret blir 10n på denna uppgift? Jag förstår verkligen inte..

Skaft 2373 – F.d. Moderator
Postad: 6 sep 2021 14:37

"så bra man kan" är lite för mycket press :D men jag kan försöka förklara, så kan du fråga vidare om det ändå är oklart.

Att algoritmens growth rate (komplexitet) är n2 betyder att dubbelt så mycket input tar fyra ggr så mycket tid att köra. Tre gånger så mycket input tar 9 ggr längre att köra, osv. Tiden växer alltså kvadratiskt med storleken på input.

På dator A tar storleken n en timme att köra. Dator B är 100 ggr snabbare än dator A, så på den snabba datorn tar storleken n bara 1/100 timme att köra. Men det är fortfarande sant att tiden kommer öka kvadratiskt när inputstorleken växer. Är storleken 2n, dvs dubbelt så stor, då tar det 4 ggr längre igen: 4/100 timme. Storleken 3n tar 9/100 timme. Hur många n klarar då datorn innan vi är uppe i en hel timmes körtid?

exer240 25
Postad: 6 sep 2021 14:55
Skaft skrev:

"så bra man kan" är lite för mycket press :D men jag kan försöka förklara, så kan du fråga vidare om det ändå är oklart.

Att algoritmens growth rate (komplexitet) är n2 betyder att dubbelt så mycket input tar fyra ggr så mycket tid att köra. Tre gånger så mycket input tar 9 ggr längre att köra, osv. Tiden växer alltså kvadratiskt med storleken på input.

På dator A tar storleken n en timme att köra. Dator B är 100 ggr snabbare än dator A, så på den snabba datorn tar storleken n bara 1/100 timme att köra. Men det är fortfarande sant att tiden kommer öka kvadratiskt när inputstorleken växer. Är storleken 2n, dvs dubbelt så stor, då tar det 4 ggr längre igen: 4/100 timme. Storleken 3n tar 9/100 timme. Hur många n klarar då datorn innan vi är uppe i en hel timmes körtid?

Sorry inte meningen o sätta press haha, men tack för förklaringen. Det känns lite klarare nu!

Laguna Online 30472
Postad: 6 sep 2021 15:07

Samma galenskap som i nån tidigare tråd: det står inte att det första programmet har någonting att göra med den senare nämnda algoritmen. Det går inte att svara på frågan.

exer240 25
Postad: 6 sep 2021 17:32
Laguna skrev:

Samma galenskap som i nån tidigare tråd: det står inte att det första programmet har någonting att göra med den senare nämnda algoritmen. Det går inte att svara på frågan.

Jag blev själv irriterad på det.. :(

Laguna Online 30472
Postad: 6 sep 2021 17:49

Uppgiften kanske var vettigt formulerad från början men sedan utsattes för redigering av någon som inte är insatt i ämnet. 

exer240 25
Postad: 8 sep 2021 14:11
Skaft skrev:

"så bra man kan" är lite för mycket press :D men jag kan försöka förklara, så kan du fråga vidare om det ändå är oklart.

Att algoritmens growth rate (komplexitet) är n2 betyder att dubbelt så mycket input tar fyra ggr så mycket tid att köra. Tre gånger så mycket input tar 9 ggr längre att köra, osv. Tiden växer alltså kvadratiskt med storleken på input.

På dator A tar storleken n en timme att köra. Dator B är 100 ggr snabbare än dator A, så på den snabba datorn tar storleken n bara 1/100 timme att köra. Men det är fortfarande sant att tiden kommer öka kvadratiskt när inputstorleken växer. Är storleken 2n, dvs dubbelt så stor, då tar det 4 ggr längre igen: 4/100 timme. Storleken 3n tar 9/100 timme. Hur många n klarar då datorn innan vi är uppe i en hel timmes körtid?

Eftersom du förklara detta så bra så ger dig ett till liknande problem som du jättegärna får förklara. Hur ska jag tänka här?

Fermatrix 7841 – Fd. Medlem
Postad: 8 sep 2021 14:16

exer240, det står I pluggakitens regler att man endast skall ha en fråga per tråd. Gör en ny tråd om du behöver hjälp med din andra uppgift. /moderator

Svara
Close