1

Złożoność obliczneniowa

Zad. 1
Korzystając z twierdzenia o rekurencji uniwersalnej podaj oszacowanie asymp-
totyczne dla:

• T (n) = 4T (n/4) + n

• T (n) = 2T (n/3) + n

• T (n) = 6T (n/4) + n

2

• T (n) = 2T (2n) + n

• T (n) = 3T (n/3) + n log(n)

Zad. 2
Napisz pseudokod operacji kolejki priortetowej (INSERT, MAXIMUM, EXTACT-
MAX) dla zwykłej kolejki (zaimplementowanej dla tablicy). Można korzystać z
procedur ENQUEUE i DEQUEUE. Oszacuj złożoność obliczeniową operacji.
Zad. 3
Napisz pseudokod procedury IN SERT (Q, i, key), która będzie wstawiała na
i-tej pozycji kolejki wartość key. Operacja ma się odbywać bez nadpisywania
żadnego z elementów (oraz bez zmieniania kolejności). Oszacuj złozoność obli-
czeniową takiej operacji.
Zad. 4
Napisz pseudokod funkcji EXT RACT (Q, i), która będzie usuwała element z
i-tej pozycji kolejki oraz zwracała jego wartość. Oszacuj złozoność obliczeniową
operacji.

2

Sortowanie

Zad. 5
Algorytmy sortowania QUICKSORT i MERGESORT to algorytmy typu dziel
i zwyciężaj. Który z nich ma mniejszy koszt scalania, dlaczego?
Zad. 8
Wykonaj algorytm PODZIAL na poniższej tabeli.

3

4

9

2

5

1

4

6

procedure PODZIAL (A, p, r)

x ← A[r]
i ← p − 1
for j ← p to r − 1

do if A[j] ¬ x

then i ← i + 1

A[i] ↔ A[j]

A[i + 1] ↔ A[r]
return i + 1

1

Zad. 9
Zmodyfikuj algorytm BUBBLE-SORT tak aby sortował nierosnąco.

for i ← 1 to n

do for j ← n downto i + 1

do if A[j] < A[j − 1]

then A[j] ↔ A[j − 1]

3

Kopce

Zad. 11
Czy lista posortowana malejąco jest kopcem typu MAX. Dlaczego?
Zad. 12
Czy lista posortowana rosnąco jest kopcem typu MAX. Dlaczego?
Zad. 13
Czy ciąg elementów jest kopcem typu MAX.

a) 21, 15, 19, 9, 10, 11, 12, 5, 4, 1, 6, 2, 4

b) 21, 15, 19, 12, 15, 11, 12, 5, 4, 1, 6, 2, 4

c) 21, 15, 19, 8, 15, 11, 12, 9, 4, 1, 6, 2, 4

Zad. 14
Co stanie się z pierwszym el. tabeli jeśli wywołamy HEAPIFY(A,1)?

a) 7, 25, 19, 19, 20, 11, 12, 6, 14, 11, 16, 2, 4

MAX-HEAPIFY(A, i) l ← LEFT(i)

r ← RIGHT(i)
if (l ¬ heap-size[A]) and (A[l] > A[i])

then L ← l
else L ← i

if (r ¬ heap-size[A]) and (A[r] > A[L])

then L ← r

if L 6= i

then A[i] ↔ A[L]

MAX-HEAPIFY(A, L)

2