Algorytmy i Struktury Danych
Ćwiczenia 0 Notacja asymptotyczna.
Dla każdego z poniższych ciągów znajdź najmniejszą liczbę k taką, że f(n) = O(n
k
).
f(n) = 6 n
2
+ 3n +20
f(n) = (n
2
+ 1)( 2n
4
+ 3n -8)
f(n) = ( n
6
+ 2n
3
+1)/(n
3
+1)
Sprawdź, która z równoś
ci jest prawdziwa:
2
n+1
= O(2
n
)
2
2n
= O(2
n
)
50n +100 = O(n)
n
3
+ 6n + 4 = O(n
6
)
Podaj przykłady ciągów a(n) i b(n) takich, że a(n) =O(n
6
), b(n)= O(n
2
) ale a(n)/b(n) nie jest O(n
4
).
Sprawdź czy z tego, że a(n)= O(c(n)) i b(n)= O(c(n)) wynika, że a(n)+b(
n)= O(c(n)).
Uporządkuj , ze względu na rosnący rząd funkcji nastepujące ciągi:
lg n
! , sin(2n), n
2
, 2
lg n
, n!, lg n