DSC00126 (8)

u;    L3;    O',

• Jaki czas jest potrzebny aby policzyć alternatywę n bitów przechowywanych w n Y&smót-Icacb pamięci r»-procesorowej maszyny Conunon-CRCW PRAM7    Q- 0(\g“nj Q-

&Qgn) O; ©(Iglgn) O; ©(lg^a«) □; ©(n) □; ©(n^a) Q;

• Jaki jest w najgorszym przypadku czas wyznaczania funkcji prefiksowej n w algorytmie Knutha-MorrisanPratta wyszukiwania wzorca długości m w tekście długości n nad alfabetem U? &(n -f- m?) □; ©(nm) O; O(m) □; ©(n. + mj O-,    ©(n -V- m\Y3£) Q\ ©(n -V

m³jUl) □; ©(nm²) O; ©(m³|X|) Q; ©((Ej -ł- m) O;

• Jaki czas jest niezbędny w najgorszym przypadku aby wyznaczyć medianą n elementów z tablicy reprezentującej kopiec binarny? ©(1) □; ©(lg*n) O-, ©(Ig n.j D-, ©(lglg n) Q-, ©(Ig²/*) O; O(n) O; B(n²) □;

• Jaki może być maksymalny czas działania operacji Find wykonanej po n operacjach algorytmu UNION-FJND? ©(Ig*n) □; ©(lglg n) Q; ©(lg²n) U\ ©(n) O; ©(n \g n) O-,

e(rty/n) O; ©(n²) □; 0(n¹⁵) □; ©(n¹⁵lgn) □; ©(1) □; ©(lgn) O;

Jaki może być maksymalny czas działania operacji "Union wykonanej po n operacjach algorytmu UNION-FJND? 0(lg*n) O; 0(lglg n) Q; 0(lg²n) D- B(n) O*, B(n \g n) Q-, S(ny/ń) U; 0(n²) □; 0(n¹⁵) □; 0(n¹⁵lgn) □; 0(1) Q- B(lgn} O;

Jaki jest (w najgorszym przypadku) faktyczny koszt wykonania ciągu n operacji Insert następujących po nich n operacji Decrease-key na początkowo pustym kopcu Yibon

dego? e(l) □; e(lg*n) □; ©(lg n) O; ©(lglg n) g| ©(lg²nj g| ©(nj O; ©fnlgnj

B(ny/n) O; ©(n²) □; ©(n¹⁸) □; ©(n¹-⁸lgn) O;

1