System
#0
Begrebet tid har vi opgivet til eksamen... vi har lært grundprincipperne, den rejsende handlers problem og har lært om algoritmiserbare problemer og ikke-algoritmiserbare problemer... vi har skrevet en rapport om "kompleksiteten af boblesort/Hvor lang tid tager det" hvor vi fik et testprogram der basically sorterede nogle tal.. vi testede så programmerne på flere forskellige computere og fandt ud af tidsforbruget kunne skrives på formlen f(n) = konstant * n^2!
Har i nogle ideer til hvordan et spørgsmål i dette emne kunne se ud... (det skal lige siges der er opgivet 15 sider om det ud af 125)
Håber i kan hjælpe!
Har i nogle ideer til hvordan et spørgsmål i dette emne kunne se ud... (det skal lige siges der er opgivet 15 sider om det ud af 125)
Håber i kan hjælpe!
#1
Hvordan et spørgsmål i det ser ud? Altså så du kan forberede dig på hvad du skal kunne svare på eller hvad?
#2
Jamen, jeg skal ikke kunne sige hvordan det ser ud, nærmere noget om hvad du skal kunne, og måske snarere noget om hvad der kan være godt at sige. Jeg læser selv datalogi på Århus Universitet. Du siger I har lavet en test på at boblesort kører ca. en eller anden konstant gange n^2. Det bruger man som regel noget der hedder store O notation til at beskrive. Man skriver at boblesort kører i tid O(n^2) (udtales: o af n^2), hvilket netop betyder at øges mængden der skal sorteres med n øges tiden det tager med n sat i anden potens. Det er et ca. tal, men da n^2 altid betyder langt mere end en eller anden konstant også selvom konstanten er meget stor bruger man den notation. Med andre ord, man smider konstanten væk og ser bort fra den, for den er ubetydelig.
Jeg tror det er vigtigt at kunne huske og gøre rede for hvad i skrev i den rapport der, det er sikkert det de vil gå op, da emnet er tid. Hvis du vil have noget mere teoretisk ind kan du også se på koden for boblesort. Den vil bestå af noget tildelinger og variabelerklæringer og herefter vil der være to løkker af en eller anden art inde i hinanden som begge kører op til n. Det betyder altså at for hvert tal fra 0 til n skal der udføres en løkke fra 0 til n og gæt hvad det giver? Ja nemlig, n^2. Derfor kan man direkte se på koden hvor hurtig algoritmen kører.
Når du så har fat i tid er det vigtigt også at understrege vigtigheden af hvor hurtigt en algoritme kører. Hvis man løser et problem i tid O(n^3) som egentlig kan løses i O(n) (altså lineær tid) har man virkelig spildt voldsomt mange ressourcer. Tænkt på hvis problemet er af størrelse 10000 (altså, hvis der f.eks er 10000 elementer der skal sorteres), så vil O(n) algoritmen kunne sortere elementerne i tiden 10000, hvor O(n^3) vil tage tiden 10000^3 = 1000000000000 altså 100 millioner gange så lang tid. Hvis så vi siger O(n) algoritmen kan sortere de 10000 elementer på 3 sekunder, så tager O(n^3) algoritmen 3*100000000 sekunder = 9,5 år om at løse samme problem. Tilgiv mig hvis jeg har regnet lidt forkert hist og her, men pointen er at lineær tid (O(n)) er LANGT LANGT LANGT LANGT LANGT bedre end kubisk tid (O(n^3)) og lineær tid er selvfølgelig også LANGT bedre end kvadratisk tid (O(n^2)), især når problemerne bliver af en vis størrelse.
En helt anden ting er, at man ikke kan sortere tilfældige elementer i lineær tid, så det var blot en antagelse jeg brugte. Den bedste sorteringsalgoritme der er kendt kører lidt hurtigere end O(n*log(n)) såvidt jeg husker.
Håber det kunne bruges selvom det sikkert er lidt snørklet at forstå, hvis man ikke lige har hørt det før. Ellers må du spørge ind til det du ikke forstår.
Jeg tror det er vigtigt at kunne huske og gøre rede for hvad i skrev i den rapport der, det er sikkert det de vil gå op, da emnet er tid. Hvis du vil have noget mere teoretisk ind kan du også se på koden for boblesort. Den vil bestå af noget tildelinger og variabelerklæringer og herefter vil der være to løkker af en eller anden art inde i hinanden som begge kører op til n. Det betyder altså at for hvert tal fra 0 til n skal der udføres en løkke fra 0 til n og gæt hvad det giver? Ja nemlig, n^2. Derfor kan man direkte se på koden hvor hurtig algoritmen kører.
Når du så har fat i tid er det vigtigt også at understrege vigtigheden af hvor hurtigt en algoritme kører. Hvis man løser et problem i tid O(n^3) som egentlig kan løses i O(n) (altså lineær tid) har man virkelig spildt voldsomt mange ressourcer. Tænkt på hvis problemet er af størrelse 10000 (altså, hvis der f.eks er 10000 elementer der skal sorteres), så vil O(n) algoritmen kunne sortere elementerne i tiden 10000, hvor O(n^3) vil tage tiden 10000^3 = 1000000000000 altså 100 millioner gange så lang tid. Hvis så vi siger O(n) algoritmen kan sortere de 10000 elementer på 3 sekunder, så tager O(n^3) algoritmen 3*100000000 sekunder = 9,5 år om at løse samme problem. Tilgiv mig hvis jeg har regnet lidt forkert hist og her, men pointen er at lineær tid (O(n)) er LANGT LANGT LANGT LANGT LANGT bedre end kubisk tid (O(n^3)) og lineær tid er selvfølgelig også LANGT bedre end kvadratisk tid (O(n^2)), især når problemerne bliver af en vis størrelse.
En helt anden ting er, at man ikke kan sortere tilfældige elementer i lineær tid, så det var blot en antagelse jeg brugte. Den bedste sorteringsalgoritme der er kendt kører lidt hurtigere end O(n*log(n)) såvidt jeg husker.
Håber det kunne bruges selvom det sikkert er lidt snørklet at forstå, hvis man ikke lige har hørt det før. Ellers må du spørge ind til det du ikke forstår.