Dzisiaj będzie trochę teorii n.t. tzw. notacji asymptotycznej. jest ona używana do szacowania złożoności obliczeniowej algorytmów, dzięki czemu można w miarę dokładnie wyznaczyć takie parametry jak czas wykonywania się określonych instrukcji, rozmiar alokowanej pamięci itp. trochę na ten temat pisałam już tutaj.
Przyjmijmy, że f(n) i g(n) są funkcjami (czyli np. czas), dla n→ ∞ , oraz g(n) jest różna od 0, n będzie parametrem wejściowym, np wielkość tablicy do przetworzenia, długość łańcucha znaków, liczba obiektów itp. Poniżej przedstawiłam część teoretyczną odnośnie najczęściej stosowanych notacji zarówno z naukach matematycznych jak i informatycznych. Na dole znajdziesz wykresy obrazujące przykładowe funkcje.
A więc zaczynamy.
Notacja O
(Czytaj „notacja duże O” lub „ograniczenie górne”)
Zapisujemy jako: f(n) = O(g(n))
Taki zapis oznacza, że f jest co najwyżej rzędu g, czyli istnieje taka stała c, że:
|f(n)| ≤ c · |g(n)|
Czyli funkcja g(n) jest ograniczeniem górnym dla f (n).
- Jak sprawdzić, czy f(n) = O(g(n)) ?
Upewniamy się, że 
a konkretniej
Przykładowy wykres:
Notacja Ω
(Czytaj „notacja duże omega” lub „ograniczenie dolne”)
Zapisujemy jako: f(n) = Ω(g(n))
Taki zapis oznacza, że f jest co najmniej rzędu g, czyli istnieje taka stała c, że:
|f(n)| ≥ c ·| g(n)|
Czyli funkcja g(n) jest ograniczeniem dolnym dla f (n).
- Jak sprawdzić, czy f(n) = Ω(g(n)) ?
Upewniamy się, że 
Notacja Θ
(Czytaj „notacja kanapkowa” lub „teta”)
Zapisujemy jako: f(n) = Θ(g(n))
Taki zapis oznacza, że f jest tego samego rzędu co g, czyli istnieją takie stałe c1 i c2 że:
c1 · |g(n)| ≤ |f(n)| ≤ c2 · |g(n)|
Czyli funkcja g(n) jest ograniczeniem górnym dla f (n).
- Jak sprawdzić, czy f(n) = Θ(g(n)) ?
Upewniamy się, że 
lub konkretniej 
Notacja o
(Czytaj „notacja małe o”)
Zapisujemy jako: f(n) = o(g(n))
Taki zapis oznacza, że f jest rzędu mniejszego niż rząd g, czyli istnieje taka stała c, że:
|f(n)| < c · |g(n)|
- Jak sprawdzić, czy f(n) = o(g(n)) ?
Upewniamy się, że 
(o ile granica istnieje)
Notacja ω
(Czytaj „notacja małe omega”)
Zapisujemy jako: f(n) = o(g(n))
Taki zapis oznacza, że f jest rzędu większego niż rząd g, czyli istnieje taka stała c, że:
|f(n)| > c · |g(n)|
- Jak sprawdzić, czy f(n) = o(g(n)) ?
Upewniamy się, że 
(o ile granica istnieje)
Notacja ~
(Czytaj „notacja falka”)
Zapisujemy jako: f(n) ~ g(n)
Taki zapis oznacza, że nie tylko f jest rzędu równego co g, ale też, że f bardzo przypomina g.
- Jak sprawdzić, czy f(n) ~ g(n) ?
Upewniamy się, że 
Wszystkie 5 najważniejszych notacji można przedstawić na schemacie:
Funkcje można uszeregować zgodnie ze wzrastającą złożonością:
f(n) = O(1) – funkcja f(n) jest ograniczona przez funkcję stałą
f(n) = O(log n) – funkcja f(n) jest ograniczona przez funkcję logarytmiczną
f(n) = O(√n)
f(n) = O(log2 n)
f(n) = O(n) – funkcja f(n) jest ograniczona przez funkcję liniową
f(n) = O(n log n)
f(n) = O(nk) – funkcja f(n) jest ograniczona przez funkcję potęgową lub wielomian
f(n) = O(an) – funkcja f(n) jest ograniczona przez funkcję wykładniczą
f(n) = O(n!) – funkcja f(n) jest ograniczona przez silnię
f(n) = O(nn) – funkcja f(n) jest ograniczona przez funkcję potęgowo-wykładniczą
A oto przykładowe wykresy dla zrozumienia o czym mowa.
Dla obliczeń zastosowałam podstawę logarytmu = 2.
Zwróć uwagę, że funkcje √n i log(n) dla niewielkich n przyjmują prawie identyczne wartości. Jednak rząd funkcji √n jest większy od logarytmicznej. Podobną sytuację mamy dla funkcji liniowej n oraz log2n (log(n)*log(n)).
Z racji odmiennej skali przyjmowanych wartości postanowiłam umieścić 3 ostatnie funkcje na osobnym wykresie:
Jak widzisz, dla stosunkowo niewielkich n, wartości funkcji wyrażają się w milionach. Funkcja nn to funkcja o najwyższej urzędowości jaką udało mi się znaleźć. Oczywiście można by rozważyć taki twór jak n!n! ale nie wiem, czy spotyka się go w realnych zastosowaniach informatycznych.
good job!
Najnowsze komentarze