Kurssiaiheen 3 tehtävät

Suorituskyky

Tarkastele alla olevien funktioiden pseudokoodeja. (Saattaa olla hyödyksi muistella lisäysjärjestämisen (insertion sort) mekanismia.) Voit olettaa, että vain kuvatut asiat vaikuttavat toimintojen suorituskykyyn (tehokkuutteen), joten esimerkiksi APPEND()-funktion suorituskyvyllä ei ole väliä.

1
2
3
4
5
6
7
8
9
  FunctionA(Array A):
    res := [[]] // empty 2D Array
    FOR i IN SIZE(A):
      FOR j IN SIZE(A):
        APPEND(res[i], A[i] * A[j])
      END LOOP
      APPEND(res, []) // Add empty array inside the 2D array
    END LOOP
    RETURN res
1
2
3
4
5
6
7
8
  FunctionB(Array A, Int target)
    FOR i IN A:
      FOR j IN A:
        IF i * j == target THEN
          RETURN [i, j]
        END IF
      END LOOP
    END LOOP
1
2
3
4
5
6
7
8
  FunctionC(Array A):
    IF SIZE(A) == 1 OR EMPTY(A) THEN
      RETURN TRUE
    ELSE IF FIRST(A) != LAST(A) THEN
      RETURN FALSE
    END IF
    POP_FIRST_AND_LAST(A) // Remove first and last elements
    FunctionC(A)
Mitkä funktiot eivät välttämättä hidastu, vaikka syötteen koko kasvaa?
Mitä voidaan sanoa FunctionB parhaan mahdollisen tapauksen syötteestä?
Ja mitä voidaan sanoa huonoimmasta tapauksesta FunctionB suhteen?
Minkä funktion osalta parhaan, huonoimman ja keskimääräisen tapauksen suorituskyvyt ovat samat?

Summa rekursiona

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

Numeroiden summa rekursiona

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