Øvingsoppgaver - Analyse av algoritmer
Oppgave 1
Oppgave 1.8 s. 27 i læreboka.
Oppgave 2
Oppgave 1.9 s. 27 i læreboka.
Oppgave 3
En algoritme tar 0.5 ms når størrelsen på datamengden N =100. Hvor stort problem kan løses på 1 minutt når vi antar at lavereordensledd er neglisjerbare og arbeidsmengden er:
- Lineær
- Kvadratisk
- Kubisk
Oppgave 4
For hvert programfragment nedenfor skal du :
- Angi arbeidsmengde i O-notasjon
- Implementer koden og kjør for forskjellige verdier av N
- Sammenlikne analyse med observert kjøretid.
Her er det lønnsomt å tenke seg litt om før man går i gang med å måle faktisk kjøretid. Noen av kodebitene vil ta veldig lang tid når N blir stor....
// Fragment 1
for (int i=0; i < n; i++)
sum++;
// Fragment 2
for (int i=0; i < n; i += 2)
sum++;
// Fragment 3
for (int i=0; i< n; i++)
for (int j=0; j < n; j++)
sum++;
// Fragment 4
for (int i=0; i< n; i++)
sum++;
for (int j=0; j< n; j++)
sum++;
// Fragment 5
for (int i=0; i< n; i++)
for (int j=0; j<n*n; j++)
sum++;
// Fragment 6
for (int i=0; i< n; i++)
for (int j = 0; j < i; j++)
sum++;
// Fragment 7
for (int i=0; i< n; i++)
for (int j=0; j< n*n; j++)
for (int k=0; k<j; k++)
sum++;
// Fragment 8
for (int i=1; i< n; i=i*2)
sum++;
