Beräkning av teoretisk tidskomplexitet
Hej, Jag har skapat min egna version av Kruskal's algoritm och min uppgift nu är att med hjälp av studera min kod komma fram till en tidskomplexitet för denna och jämföra om den är lika bra som Kruskal's algoritm ska vara.
Problemet är att jag har svårt för att beräkna detta, Några tips på källor eller hjälp för att jag ska kunna förstå detta bättre.
/Pehr
Ett förslag, beräkna tiden ditt program tar för att gå igenom N st element sedan tiden för 2N o.s.v så många gånger du behöver dubblera datamängden. Gör en graf med tiden på y-axeln och antalet element N på x-axeln. Approximera en kurva så gott det går. Säg att kurvan som passar in på mätpunkterna är ett andragradspolynom. Då är tidskomplexiteten för ditt program .
Tidskomplexiteten för en algoritm i teorin är den bästa tidskomplexiteten som går att få med den algoritmen. Tidskomplexiteten för en implementation av algoritmen blir något annat eftersom det beror mycket på hur genomtänkt implementationen är, utnyttjas minnet på rätt sätt, o.s.v . Bara en sådan sak som olika programmeringsspråk är olika snabba
Aerius skrev:Ett förslag, beräkna tiden ditt program tar för att gå igenom N st element sedan tiden för 2N o.s.v så många gånger du behöver dubblera datamängden. Gör en graf med tiden på y-axeln och antalet element N på x-axeln. Approximera en kurva så gott det går. Säg att kurvan som passar in på mätpunkterna är ett andragradspolynom. Då är tidskomplexiteten för ditt program .
Tidskomplexiteten för en algoritm i teorin är den bästa tidskomplexiteten som går att få med den algoritmen. Tidskomplexiteten för en implementation av algoritmen blir något annat eftersom det beror mycket på hur genomtänkt implementationen är, utnyttjas minnet på rätt sätt, o.s.v . Bara en sådan sak som olika programmeringsspråk är olika snabba
Ah super duper! men när jag då ska klocka tiden hade du haft med inläsning av filer och utskrift osv eller enbart min algoritm som är en egen funktion så då bara haft tiden på just den funktionen?
Vid inläsning Har jag två grejer noder och länkar så säg att mitt N är 100 så kan mitt E vara 100 eller 1000 osv. Hur gör jag då? för man kan säga att jag har två olika N som gör att körtiden blir annorlunda
Isolera algoritmen så mycket som möjligt från in/ut läsning av data, andra delar av programmet som inte har med algoritmen. Om det är svårt att isolera algoritmen kan den köras med minimalt med data så själva algoritmen går fort. På så sätt fås en grov uppskattning av hur snabbt det övriga programmet går.
Jag är inte påläst om Kruskals algoritm, hur N och E påverkar varandra vet jag inte. Om det är svårt att tidsbestämma delar av programmet kan det vara idé att skriva om och dela upp programmet mer. Annars ta tid för hela programmet, hitta tidskomplexiteten och jämför med det teoretiska. Det kanske kommer nära det teoretiska och då finns det inte mycket att förbättra ändå.
Att provköra med slumpade indata kan vara bra, men det går inte att avgöra maximala tiden på det viset.
