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.