Oppgavesett 2

Fra Hiofwiki

Innhold 1 Løsningsforslag (Gruppe 3) 1.1 Oppgave 1 1.2 Oppgave 2 1.3 Oppgave 3 1.4 Oppgave 4 2 Løsningsforslag (Gruppe N) 2.1 Oppgave 1 2.2 Oppgave 2 2.3 Oppgave 3 2.4 Oppgave 4

Oppgavesett

Løsningsforslag (Gruppe 3)

Linker til filer:
FragmentTester.java
Modul02.pdf

Oppgave 1

• Hvilken orden er det på de følgende funksjonene? (Oppgave 1.8 s. 27 i læreboka.)

---

A

10n² + 100n + 1000 er av orden O(N²)

B

10n³ - 7 er av orden O(N³)

C

2n + 100n³ er av orden O(N³)

D

n² log n er av orden O(N²).

Oppgave 2

• Arranger funksjonene fra oppgave 1 i stigende rekkefølge etter effektivitet (raskeste arbeidstid) når N = 10 og N = 1000000 (Oppgave 1.9 s. 27 i læreboka.)

---

N = 10

1. O(N²)
2. O(N³)
3. O(N log N)

N = 1000000

1. O(N log N)
2. O(N²)
3. O(N³)

Valg av algoritme er mindre viktig ved små verdier av N, pga. liten forskjell mellom den raskeste og den tregeste algoritmen.
Ved store verdier av N er det mye mer viktig å velge riktig algoritme siden forskjellene kan her være fra noen timer (kanskje noen dager) med raskeste algoritme til flere år (mot uendelig) med den tregeste algoritmen.
Litt mer informasjon om algoritmevalg Coding Horror

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:

1. Lineær
   
2. Kvadratisk
   
3. Kubisk

---

Lineær

1 minutt = 60 sekunder = 60 000 millisekunder

Konstantleddet C:  
T(N) = C × N 
T(100) = 0.5ms 
C × N = 0.5ms
100 × C = 0.5ms
C = 0.5/100 = 0.005

Arbeidsmengde:
C × N = 60000
N = 60000/C = 60000/0.005 = 12000000 = 12 × 106

Kvadratisk

Konstantleddet C:
T(N) = C × N2
T(100) = 0.5ms 
C × N2 = 0.5ms
1002 × C = 0.5ms
C = 0.5/1002 = 0.00005

Arbeidsmengde: 
C × N2 = 60000
N2 = 60000/C = √60000/C = 20000 × √3 ≈ 34641

Kvadratisk

Konstantleddet C:
T(N) = C × N3
T(100) = 0.5ms 
C × N3 = 0.5ms
1003 × C = 0.5ms
C = 0.5/1003 = 0.0000005

Arbeidsmengde:
C × N3 = 60000
N3 = 60000/C = 3√60000/0.0000005 = 20000 × 3√15 ≈ 4932

Oppgave 4

• For hvert programfragment nedenfor skal du:

1. Angi arbeidsmengde i O-notasjon
   
2. Implementer koden og kjør for forskjellige verdier av N
   
3. Sammenlikne analyse med observert kjøretid
   

---

1. O-notasjon for hvert fragment

• Fragment 1:

  for (int i=0; i < n; i++) 
    sum++;

O-notasjon: O(N) [Lineær]

• Fragment 2:

 for (int i=0; i < n; i += 2)
   sum++;

O-notasjon: O(N) [Lineær]

• Fragment 3:

for (int i=0; i< n; i++)
  for (int j=0; j < n; j++)
    sum++;

O-notasjon: O(N²) [Kvadratisk]

• Fragment 4:

for (int i=0; i< n; i++) 
  sum++; 
for (int j=0; j< n; j++) 
  sum++;

O-notasjon: O(N) [Lineær]

• Fragment 5:

for (int i=0; i< n; i++) 
  for (int j=0; j<n*n; j++)
    sum++;

O-notasjon: O(N³) [Kubisk]

• Fragment 6:

for (int i=0; i< n; i++)
  for (int j = 0; j < i; j++)
    sum++;

O-notasjon: O(N²) [Kvardratisk]

• 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++;

O-notasjon: O(N⁵) [Høyere orden]

• Fragment 8:

for (int i=1; i< n; i=i*2)
  sum++;

O-notasjon: O(log N) [Logaritmisk]

2. Implementert java kode:

               // ORDER: O(N) - Linear
               // Starting the clock 
               start = System.currentTimeMillis();

               // Sets a value to the variable n
               n = 1000000;

               // Implemented fragment 1
               for(int i=0; i < n; i++){
                   sum++;
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Denne gjennomkjøringen med lineære orden av N ble kjørt med N lik 1000000, 10000000, 100000000, 1000000000.

               // ORDER O(N^2) - Quadratic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 1000;

               // Implemented fragment 3
               for(int i=0; i < n; i++){
                 for(int j=0; j < n; j++){
                   sum++;
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Denne gjennomkjøringen med kvadratisk orden av N ble kjørt med N lik 1000, 10000, 50000, 100000.

               // ORDER O(N^3) - Cubic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 100;

               // Implemented fragment 5
               for(int i=0; i < n; i++){
                 for(int j=0; j < n*n; j++){
                   sum++;
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Denne gjennomkjøringen med kubisk orden av N ble kjørt med N lik 100, 500, 1000, 2000.

               //ORDER O(N^5) - Higher order
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 10;

               // Implemented 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++;
                   }
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Denne gjennomkjøringen med høyere orden av N ble kjørt med N lik 10, 15, 100, 115.

               //ORDER O(log N) - Logarithmic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 10000000;

               // Implemented fragment 8
               for(int i=1; i < n; i=i*2){
                 sum++;
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Denne gjennomkjøringen med logaritmisk orden av N ble kjørt med N lik 10000000, 100000000, 1000000000.

3. Sammenlikne analyse med observert kjøretid
Fragment 1:

Antall operasjoner      Tid
1000000                 O ms
10000000                47 ms
100000000               375 ms
1000000000              3782 ms

O-notasjonen: O(N) [Lineær]
Av listen over kjøretiden ser en at de øker lineær, og dette stemmer overens med O-notasjonen.

Fragment 3:

Antall operasjoner      Tid
1000                    O ms
10000                   375 ms
50000                   9453 ms
100000                  37703 ms

O-notasjonen: O(N²) [Kvadratisk]
Av listen over kjøretiden ser en at de øker kvadratisk, og dette stemmer overens med O-notasjonen.

Fragment 5:

Antall operasjoner      Tid
100                     O ms
500                     532 ms
1000                    4328 ms
2000                    38906 ms

O-notasjonen: O(N³) [Kubisk]
Av listen over kjøretiden ser en at de øker kubisk (realtivt hurtig økning), og dette stemmer overens med O-notasjonen.

Fragment 7:

Antall operasjoner      Tid
10                      O ms
50                      500 ms
100                     16125 ms
115                     32531 ms

O-notasjonen: O(N⁵) [Høyere orden]
Av listen over kjøretiden ser en at de øker meget hurtig, og dette stemmer overens med O-notasjonen.

Fragment 8:

Antall operasjoner      Tid
10000000                O ms
100000000               0 ms
1000000000              0 ms

O-notasjonen: O(log N) [Logaritmisk]
Her er kjøretiden så ekstrem rask at ved bruk av vanlig int verdier finner den en kjøretid lik 0 ms.

Løsningsforslag (Gruppe N)

Oppgave 1

A

10n² + 100n + 1000 =>O(N²)

B

10n³ - 7 => O(N³)

C

2n + 100n³ => O(N³)

D

n² log n => O(N²).

Oppgave 2

N = 10

1. O(N²)
2. O(N³)
3. O(N log N)

N = 1000000

1. O(N log N)
2. O(N²)
3. O(N³)

Ser her at valget av algoritme ikke er viktig for kjøretiden ved liten N med den maskinkraft som er tilgjengelig i dag. Ved store verdier blir forskjellene større, da det setter et krav til valget av algoritme.

Oppgave 3

Lineær

1 minutt = 60 000 ms

Konstantleddet C:  
T(N) = C × N 
T(100) = 0.5ms 
C × N = 0.5ms
100 × C = 0.5ms
C = 0.5/100 = 0.005

Arbeidsmengde:
C × N = 60000
N = 60000/C = 60000/0.005 = 12000000 = 12 × 106

Kvadratisk

Konstantleddet C:
T(N) = C × N2
T(100) = 0.5ms 
C × N2 = 0.5ms
1002 × C = 0.5ms
C = 0.5/1002 = 0.00005

Arbeidsmengde: 
C × N2 = 60000
N2 = 60000/C = √60000/C = 20000 × √3 ≈ 34641

Kvadratisk

Konstantleddet C:
T(N) = C × N3
T(100) = 0.5ms 
C × N3 = 0.5ms
1003 × C = 0.5ms
C = 0.5/1003 = 0.0000005

Arbeidsmengde:
C × N3 = 60000
N3 = 60000/C = 3√60000/0.0000005 = 20000 × 3√15 ≈ 4932

Oppgave 4

1. O-notasjon for hvert fragment

• Fragment 1:

  for (int i=0; i<n; i++) 
    sum++;

O-notasjon: O(N) [Lineær]

• Fragment 2:

 for (int x=0; x<n; x+=2)
   sum++;

O-notasjon: O(N) [Lineær]

• Fragment 3:

for (int i=0; i<n; i++)
  for (int j=0; j< n; j++)
    sum++;

O-notasjon: O(N²) [Kvadratisk]

• Fragment 4:

for (int x=0; x<n; x++) 
  sum++; 
for (int y=0; y<n; y++) 
  sum++;

O-notasjon: O(N) [Lineær]

• Fragment 5:

for (int k=0; k< n; k++) 
  for (int l=0; l<n*n; l++)
    sum++;

O-notasjon: O(N³) [Kubisk]

• Fragment 6:

for (int i=0; i< n; i++)
  for (int j = 0; j < i; j++)
    sum++;

O-notasjon: O(N²) [Kvadratisk]

• 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++;

O-notasjon: O(N⁵) [Orden høyere enn kubisk!]

• Fragment 8:

for (int i=1; i< n; i=i*2)
  sum++;

O-notasjon: O(log N) [Logaritmisk]

2. Implementert java kode:

               // ORDER: O(N) - Linear
               // Starting the clock 
               start = System.currentTimeMillis();

               // Sets a value to the variable n
               n = 1000000; // 1.000.000

// n = 10000000; // n = 100000000; // n = 1000000000;

               // Implemented fragment 1
               for(int i=0; i<n; i++){
                   sum++;
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Lineære orden av N kjørt med N = 1000000, 10000000, 100000000, 1000000000.

               // ORDER O(N^2) - Quadratic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 1000;

// n = 10000; // n = 50000; // n = 100000;

               // Implemented fragment 3
               for(int j=0; j<n; j++){
                 for(int k=0; k<n; k++){
                   sum++;
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Kvadratisk orden av N kjørt med N = 1000, 10000, 50000, 100000.

               // ORDER O(N^3) - Cubic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 100;

// n = 500; // n = 1000; // n = 2000;

               // Implemented fragment 5
               for(int l=0; l<n; l++){
                 for(int m=0; m<n*n; m++){
                   sum++;
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Kubisk orden av N kjørt med N = 100, 500, 1000, 2000.

               //ORDER O(N^5) - Higher order
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 10;

// n = 15; // n = 100; // n = 115;

               // Implemented 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++;
                   }
                 }
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Orden høyere enn kubisk av N kjørt med N = 10, 15, 100, 115.

               //ORDER O(log N) - Logarithmic
               start = System.currentTimeMillis();

               // Sets a value to the var n
               n = 10000000;

// n = 100000000; // n = 1000000000;

               // Implemented fragment 8
               for(int i=1; i < n; i=i*2){
                 sum++;
               }

               stop = System.currentTimeMillis();
               System.out.println("| N: " + n + " | Tid: " + (stop - start) + " millisekunder ");

Logaritmisk orden av N kjørt med N = 10000000, 100000000, 1000000000.

3. Sammenlikne analyse med observert kjøretid
Fragment 1:

Antall operasjoner      Tid
1000000                 O ms
10000000                55 ms
100000000               413 ms
1000000000              5001 ms

O-notasjonen: O(N) [Lineær]
Lineær økning stemmer med O(N).

Fragment 3:

Antall operasjoner      Tid
1000                    O ms
10000                   402 ms
50000                   8992 ms
100000                  39644 ms

O-notasjonen: O(N²) [Kvadratisk]
Kvadratisk økning stemmer med O(N².

Fragment 5:

Antall operasjoner      Tid
100                     O ms
500                     547 ms
1000                    4447 ms
2000                    41109 ms

O-notasjonen: O(N³) [Kubisk]
Kubisk økning stemmer med O(N³!

Fragment 7:

Antall operasjoner      Tid
10                      O ms
50                      499 ms
100                     18222 ms
115                     33954 ms

O-notasjonen: O(N⁵) [Orden høyere enn kubisk]
En høyere orden stemmer her, veldig rask økning!

Fragment 8:

Antall operasjoner      Tid
10000000                O ms
100000000               0 ms
1000000000              0 ms

O-notasjonen: O(log N) [Logaritmisk]
Kjedelig, burde brukt større verdier for å se om man fikk en innvirkning på log N.