DSC00127 (12)

•f&fci 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 dwvomar r nowym? 0(1) O; ©(lg*n) O; ©(lg _n) O; ©(lglg o) C3; ©(lg²n) O; ©(-oj Q- ©(n\gn) O; &(ny/n) O; ©(n³) O; ©(n¹ ■») □; ©(_n^1Blgn) □;

Które z poniższych jest najdokładniejszym dolnym ograniczeniem na iiczfo^ porównań potrzebnych (w najgorszym przypadku) do scalenia posortowanego ciągu rv elementowego I posortowanym ciągiem (n^ł^³)-elementowym? fl(l) □; fl(n) O; tl(y/n) O*, ft^nlogn) Q-D; 12 (ra²) O; 0(n³) □;

1    jest co najmniej komparatorów w sieci znajdującej minimum w meposoTtommp pgn n-elementowym? ©(«) O; ©(lg n) O; ©(n²) D; 0(n lg n) O; ©Qg² n) 1 nlg²n) O;

jest co najmniej komparatorów w sieci znajdującej n/4 najmniejszych, eiementó posortowanym ciągu n-elementowym? 0(n) O; ©(lg n) O; ©(ri²) Q- ©(n lg t

²    rej O; G(nlg²n) O;

| najmniej jest komparatorów w sieci scalającej dwa posortowane ciągi, tu O(n) O; S(lgn) O; S(n²) □; ©(nlgn) □; ©(lg²n) O; e{nlg²n) U\

mi w najgorszym przypadku jest wykonywanych w operacji wstawiania mo drzewa czerwono-czarnego? 0(n) □; ©(lg n) O; ©(n lg n)

E fi(lgn) O;