1.Uporządkować poniższe funkcje według rosnącej złożnośći czasowej:
\(\displaystyle{ f_1(n)=logn \ f_2(n)=loglogn \ f_3(n)=n/logn \ f_4(n)=\sqrt{n} log^2n}\)
\(\displaystyle{ a) \ f_1(n), f_2(n), f_3(n), f_4(n)
\\ b) \ f_2(n), f_1(n), f_3(n), f_4(n)
\\ c) \ f_2(n), f_3(n), f_1(n), f_4(n)
\\ d) \ f_2(n), f_3(n), f_4(n), f_1(n)}\)
I tu mam pytanie - jak ze sobą można porównywać złożoność takich funkcji w których jest log?
2. Które z poniższych zdań jest prawdziwe:
a) w kopcu binarnym liczba wszystkich liści jest nie mniejsza niż liczba pozostałych węzłów
b) w drzewie czerwono-czarnym etykiety wszystkich dróg od korzenia do liścia tworzą ciąg uporządkowany
c) w drzewie BST wszystkie drogi od korzenia do liścia mają tę samą długość
d) etykiety na każdym poziomie kopca binarnego tworzą ciągi uporządkowane
3. Do poniższego drzewa czerwono-czarnego wstawiono węzeł z wartośćią 4. W drzewie otrzymanym po wykonaniu wymaganej korekty:
a) poprzednikiem czarnego węzła 2 jest czerwony węzeł 7;
b) poprzednikiem czerwonego węzła 8 jest czarny węzeł 11;
c) poprzednikiem czerwonego węzła 5 jest czarny węzeł 2;
d) poprzednikiem czerwonego węzła 11 jest czarny węzeł 7