Kurssiaiheen 5 tehtävät

iso-O notaatio

Funktioissa parametrinä otettavan vektorin v koko on N. Valitse aina vastaukseksi mahdollisimman tiukka arvio.

1
2
3
4
5
6
   Mean(Vector v):
     int sum = 0
     FOR elem IN v :
       sum = sum + elem
     END LOOP
     RETURN sum/SIZE(v)

Mikä on funktion Mean() tehokkuus?

1
2
3
4
5
6
   MeanOfRange(Vector v, int index1, int index2):
     int sum = 0
     FOR elem IN RANGE FROM index1 TO index2 :
       sum = sum + elem
     END LOOP
     RETURN sum/(index2-index1 +1)

Oletetaan, että index1 ja index2 ovat mielivaltaisia positiivisia kokonaislukuja siten, että index1 <= index2. Mikä on MeanOfRange()-funktion tehokkuus?

1
2
3
4
5
6
7
   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"

Mikä on funktion FindIfOutliers() tehokkuus (Mean()-funktio on annettu ensimmäisessä kysymyksessä)?

Asymptoottisen tehokkuuden selvittäminen

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 Mystery1(Array[a1, a2, ... , aN]):
   B := []
   FOR elem IN Array LOOP
     IF first THEN
       B[0] := elem
     ELSEIF elem > LAST(B)
       APPEND(B, elem)
     END IF
   END LOOP
   RETURN  B
Oletetaan, että APPEND-funktio suoritetaan vakioajassa (eli Θ(1)). Mystery1-algoritmin aikavaativuus on
Jos APPEND-funktio olisikin pahimmassa tapauksessa lineaarinen, eli O(N), mutta kuitenkin keskimäärin vakio, mikä vaikutus sillä olisi koko algoritmin tehokkuuteen?
1
2
3
4
5
6
7
8
FindAPair(Array A, Array B):
  FOR a_index IN A LOOP
    FOR b_index IN B LOOP
      IF A[a_index] == B[b_index] THEN
        RETURN (a_index, b_index)
      END IF
    END LOOP
  END LOOP
Mitkä seuraavista antaa tiukimmat rajat FindAPair-algoritmin tehokkuudelle? Huomaa, että voit olettaa, että SIZE(A) == SIZE(B).
1
2
3
4
5
6
  Mean(Vector v):
    int sum = 0
    FOR elem IN v :
      sum = sum + elem
    END LOOP
    RETURN sum/SIZE(v)
Kun N on parametrin v koko, mikä on Mean()-funktion tehokkuus? (Valitse tiukin raja.)
1
2
3
4
5
6
  MeanOfRange(Vector v, int index1, int index2):
    int sum = 0
    FOR elem IN RANGE FROM index1 TO index2 :
      sum = sum + elem
    END LOOP
    RETURN sum/(index2-index1 + 1)
Oletetaan, että index1 ja index2 ovat mielivaltaisia positiivisia kokonaislukuja siten, että index1 <= index2. Kun N on parametrin v koko, mikä on MeanOfRange()-funktion tehokkuus? (Valitse tiukin raja.)
1
2
3
4
5
6
7
   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"
Kun N on parametrin v koko, mikä on FindIfOutlier()-funktion tehokkuus? (Valitse tiukin raja.)
1
2
3
4
5
6
RecursiveSum(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSum(N - 1)
  ELSE
    RETURN 1
  END IF
1
2
3
4
5
6
RecursiveSumEveryThird(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSumEveryThird(N - 3)
  ELSE
    RETURN 1
  END IF
Mikä on RecursiveSum-algoritmin tehokkuus?
Mikä alla olevista on totta, kun RecursiveSum ja RecursiveSumEveryThird -algoritmeille annetaan sama syöte?

Toistoharjoitus algoritmeista & tehokkuuksista

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.