Kurssiaiheen 5 tehtävät¶

iso-O notaatio¶

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

Kysymys 1

   Mean(Vector v):
     int sum = 0
     FOR elem IN v :
       sum = sum + elem
     END LOOP
     RETURN sum/SIZE(v)

Mikä on funktion Mean() tehokkuus?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Kysymys 2

   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?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Kysymys 3

   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ä)?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Asymptoottisen tehokkuuden selvittäminen¶

 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

Kysymys 1

Oletetaan, että APPEND-funktio suoritetaan vakioajassa (eli Θ(1)). Mystery1-algoritmin aikavaativuus on

Aina lineaarinen, eli O(N), Ω(N) ja Θ(N).

O(N), Ω(1) ja määrittelemätön Θ.

O(N), Ω(1) ja Θ(N).

Kysymys 2

Jos APPEND-funktio olisikin pahimmassa tapauksessa lineaarinen, eli O(N), mutta kuitenkin keskimäärin vakio, mikä vaikutus sillä olisi koko algoritmin tehokkuuteen?

Mikään ei muuttuisi.

Algoritmin tehokkuus kaikissa tapauksissa N-kertaistuisi.

Algoritmin huonoin tapaus olisi O(N ²) ja Θ olisi määrittelemätön.

Algoritmin huonoin tapaus olisi O(N ²), Θ ja Ω pysyvät samana.

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

Kysymys 3

Mitkä seuraavista antaa tiukimmat rajat FindAPair-algoritmin tehokkuudelle? Huomaa, että voit olettaa, että SIZE(A) == SIZE(B).

O(N)

O(N log N)

O(N ²)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Θ(N)

Θ(N log N)

Θ is undefined.

  Mean(Vector v):
    int sum = 0
    FOR elem IN v :
      sum = sum + elem
    END LOOP
    RETURN sum/SIZE(v)

Kysymys 4

Kun N on parametrin v koko, mikä on Mean()-funktion tehokkuus? (Valitse tiukin raja.)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

  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)

Kysymys 5

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)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

   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"

Kysymys 6

Kun N on parametrin v koko, mikä on FindIfOutlier()-funktion tehokkuus? (Valitse tiukin raja.)

Ω(1)

Ω(log N)

Ω(N)

Ω(N log N)

Ω( N ²)

RecursiveSum(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSum(N - 1)
  ELSE
    RETURN 1
  END IF

RecursiveSumEveryThird(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSumEveryThird(N - 3)
  ELSE
    RETURN 1
  END IF

Kysymys 7

Mikä on RecursiveSum-algoritmin tehokkuus?

O(1)

O(log N)

O(N)

O(N log N)

O( N ²)

Kysymys 8

Mikä alla olevista on totta, kun RecursiveSum ja RecursiveSumEveryThird -algoritmeille annetaan sama syöte?

RecursiveSum ja RecursiveSumEveryThird -algoritmien suoritusajat ovat samat ja niiden asymptoottinen tehokkuus on sama.

RecursiveSum ja RecursiveSumEveryThird -algoritmien suoritusajat eroavat, mutta niiden asymptoottinen tehokkuus on sama.

RecursiveSum ja RecursiveSumEveryThird -algoritmien suoritusajat ovat samat, mutta niillä on eri asymptoottinen tehokkuus.

RecursiveSum ja RecursiveSumEveryThird -algoritmien suoritusajat eroavat, ja niillä on eri asymptoottinen tehokkuus.

Toistoharjoitus algoritmeista & tehokkuuksista¶

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