Studia Licencjackie / Inżynierskie

Algorytmy i struktury danych

Lista zadań nr 4

1. Dane są następujące zależności rekurencyjne:

a. A(n) = 2A(n/2) + n dla n > 1

A(1) = 1

b. B(n) = B(n/2) + 1 dla n > 1

B(1) = 1

c. C(n) = 2C(n/2) + 1 dla n > 1

C(1) = 1

Twoje zadanie:

- Policz wartości A(64), B(64), C(64).

- Podaj, które z funkcji A, B, C można oszacować jako O(log n), O(n log n), O(n).
- Dla każdej z funkcji A, B, C podaj przykład algorytmu prezentowanego w ramach

wykładu lub na liście ćwiczeniowej, którego złożoność czasową można opisać tą
funkcją.

2. Sortujemy metodą Quicksort ciąg złożony z 10 elementów. Przedstaw:

a. drzewo wywołań rekurencyjnych dla przypadku, gdy algorytm będzie działał

najdłużej (gdy mamy „najgorsze” wyniki partition),

b. drzewo wywołań rekurencyjnych dla przypadku, gdy algorytm będzie działał

najkrócej (gdy mamy „najlepsze” wyniki partition).

3. Jak zadziała algorytm Quicksort uruchomiony dla ciągu:

a. uporządkowanego,
b. odwrotnie uporządkowanego (od największej do najmniejszej),
c. ciągu złożonego z wielu powtórzeń jednego, tego samego elementu.

Przyjmij, że procedura partition wybiera pierwszy element rozważanego podciągu jako
wartość do podziału.

4. [*] Zaimplementuj algorytm Quicksort bez użycia rekurencji.

Wskazówka: jeśli znasz strukturę nazywaną stosem, spróbuj ją wykorzystać w tym
zadaniu.