Föreläsning 1 Flashcards
1
Q
Vad är en algoritm?
A
En algoritm är en beskrivning av hur en ide kan användas för att lösa ett problem med hjälp av ett datorprogram, men behöver inte vara relaterat till datorprogram. Exempelvis Euklides algoritm.
2
Q
Vad behöver man för att bestämma tidskomplexitet?
A
- För att bestämma tidskomplexitet gäller det att hitta de operationerna som dominerar för Körtiden.
- Studera hur många gånger de högst utförs för olika typer av indata, eller ibland i medelfall eller som minst om vi vill ha en undre gräns.
- Ta fram ett överskådligt matematiskt uttrycks som bevisar att det är ett bra mått på hur många gånger operationer körs.
3
Q
Om N inte är stort varför spelar tidskomplexitet inte roll?
A
Om N inte är stort så spelar inte tidskomplexiteten inte särskilt stor roll, det kommer gå fort oavsett vad.
4
Q
Vad är en algoritms tidskomplexitet?
A
En matematisk funktion som ger ett mått på hur lång tid det tar att utföra algoritmen
5
Q
Vi har en funktion:
T(N) = 5N2
Vilket eller vilka av följande är sant om T(N)?
A
- Den är polynomiell i N
- Den är kvadratisk i N
6
Q
Är ett program en algoritm?
A
Ett program är en implementation av en eller flera algoritmer.
