Studia Licencjackie / Inżynierskie Algorytmy i struktury danych

Lista zadań nr 1

1. Sprawdź czy zachodzą zależności:

a. n 2 = O(2 n)

b. 2 n = O( n 2)

c. 100 n 2+13 n+10 = O( n 3) d. 100 n 2+13 n+10 = O( n 2) e. 100 n 2+13 n+10 = O( n) f. 10 n log n + 5 n = O( n 2) 2. Napisz funkcję w C, która wyznaczy wartość wyrażenia n

1

suma = ∑

!

1 k

k =

gdzie n jest argumentem funkcji. Wyznacz złożoność czasową Twojego rozwiązania.

3. Napisz funkcję w C, która wyznaczy wartość wyrażenia n

= ∑ k

suma

k

1 n

k =

gdzie n jest argumentem funkcji. Wyznacz złożoność czasową Twojego rozwiązania.

4. Dany jest następujący algorytm:

Specyfikacja

Dane: liczba naturalna n i ciąg a …

1

an liczb całkowitych (zapisany w tablicy a) Wynik: ......................................................................................................................................

Algorytm:

for(i=0; i<n; i++){

d[i]=0;

for(j=0; j<n; j++) if (a[j]==a[i]) d[i]++;

}

Dla tego algorytmu:

a) uzupełnij specyfikację,

b) wyznacz złożoność czasową.

5. Podaj algorytm (specyfikację i implementację) upraszczający ułamek n/ m. Oszacuj jego złożoność czasową.

Uwaga: aby uprościć ułamek, wystarczy licznik i mianownik podzielić przez ich największy wspólny dzielnik.

6. Podaj algorytm (specyfikację i implementację), który dla ciągu zer i jedynek c1, …, cn wyznacza wartość liczby o zapisie binarnym c1 c2 … cn. Ile mnożeń i dodawań wykonuje Twój algorytm?

Uwaga: skorzystaj z faktu, że wartość((c1…ck+1)2) = 2⋅wartość((c1…ck)2) + ck+1, czyli

„doczytując” kolejne cyfry można uaktualniać wartość reprezentowanej liczby.

Przykład: wartość (1011012) = 2⋅wartość(101102) + 1 = 45

7. Wyznacz wartości wykładnika k z przedziału [513, 1024], dla których algorytm szybkiego potęgowania podany na wykładzie wykona: a. najwięcej mnożeń

b. najmniej mnożeń

W odpowiedziach do punktów a. i b. podaj wartość k, liczbę wykonanych mnożeń i potęgi liczby m, które będą domnażane do wyniku (czyli zmiennej wynik).