��1 ZBo|ono[ obliczneniowa
Zad. 1
Korzystajc 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) + n2
" 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 zwykBej kolejki (zaimplementowanej dla tablicy). Mo|na korzysta z
procedur ENQUEUE i DEQUEUE. Oszacuj zBo|ono[ obliczeniow operacji.
Zad. 3
Napisz pseudokod procedury INSERT (Q, i, key), kt�ra bdzie wstawiaBa na
i-tej pozycji kolejki warto[ key. Operacja ma si odbywa bez nadpisywania
|adnego z element�w (oraz bez zmieniania kolejno[ci). Oszacuj zBozono[ obli-
czeniow takiej operacji.
Zad. 4
Napisz pseudokod funkcji EXT RACT (Q, i), kt�ra bdzie usuwaBa element z
i-tej pozycji kolejki oraz zwracaBa jego warto[. Oszacuj zBozono[ 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 sortowaB nierosnco.
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 malejco jest kopcem typu MAX. Dlaczego?
Zad. 12
Czy lista posortowana rosnco jest kopcem typu MAX. Dlaczego?
Zad. 13
Czy cig 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 wywoBamy 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 = i
then A[i] �! A[L]
MAX-HEAPIFY(A, L)
2
Wyszukiwarka
Podobne podstrony:
Złożoność obliczeniowa Zadania 2Złożoność obliczeniowa trudne zadaniazłożoność obliczeniowa algorytmu Maszyny TuringaMIARY ZLOZONOSCI OBLICZENIOWEJobliczenia zadania 5obliczenia zadania 2Algorytmy i struktury danych 02 Rekurencja i złożoność obliczeniowaniweleta obliczenia rzednych luku pionowego teoria zadania1reakcje zlozone zadaniaZadania obliczenioweobliczenia cwiczenia 1 zadania z odpowiedziami niestacjonarneZadanie 2 Wykresy sił przekrojowych w belce złożonejZadania ze zlozonosci algorytmicznychwięcej podobnych podstron