algorytm.org

Rzędy wielkości funkcji

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Rzędy wielkości funkcji
Ocena użytkowników:***** / 107
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 19:11

Rząd wielkości służy do opisu czasu działania algorytmu. Istnieją 3 notacje służące do tego celu.
1. Notacja O (omikron).
Jest to ograniczenie funkcji od góry. Gdy mówimy, że pewna f(n) funkcja jest rzędu g(n), co zapisujemy f(n)=O(g(n)), znaczy to, że istnieje taki argument n0, od którego począwszy dla każdego niemniejszego od n0 wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c. Brzmi to trochę skomplikowanie, więc zademonstruję to na przykładzie:
Image
Na prawo od punktu od n0 funkcja f(n) znajduje się pod funkcją c.g(n), czyli jest przez nią ograniczona z góry.

Jest to asymptotyczna granica górna. Służy do szacowania czasu działania algorytmu w przypadku pesymistycznym.
2. Notacja Θ (theta)
Notacja ta ogranicza funkcję f(n) od góry, tak jak notacja O oraz dodatkowo od dołu. Oznacza to, że jeżeli f(n)=Θ(g(n)) to istnieje taki argument n0, od którego począwszy dla każdego argumenu od niego niemniejszego:
  • wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnościądo stałej c1
  • wartości funkcji f(n) są niemniejsze od wartości funkcji g(n) z dokładnościądo stałej c2

I znów przykład:
Image
Na prawo od punktu od n0 funkcja f(n) znajduje się pod funkcją c1.g(n), czyli jest przez nią ograniczona z góry i nad funkcją c2.g(n), czyli jest przez nią ograniczona z dołu

Jest to asymptotyczne oszacowanie dokładne.
3. Notacja Ω (omega).
Notacja ta ogranicza funkcję f(n) od dołu. Oznacza to, że jeśli f(n)=Ω(g(n)) to istnieje taki argument n0, od którego począwszy dla każdego argumenu od niego niemniejszego funkcja f(n) jest niemniejsza niż g(n) z dokładnościądo stałej c:
Image
Na prawo od punktu od n0 funkcja f(n) znajduje się nad funkcją c.g(n).
Jest to asymptotyczna granica dolna. Służy więc do oszacowania działania algorytmu w najlepszym przypadku.
Zobacz też złożoność obliczeniowa

Poprawiony: 15 sierpnia 2005 23:54
Komentarze
photo
+5 # student 2009-10-03 15:06
Wielki dzięki za art. Przyda się na kolokwium !
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # + 2010-08-06 13:51
wykresy na duży plus.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # Lolcio 2011-01-14 23:16
uffffff...dobrze ze to znalazłem :) bo z "wprowadzenia do algorymów" Cormena nic nie da sie zrozumieć :) Dzięki :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # kt1117 2011-09-09 20:30
Zgadzam się z tym, że wprowadzenie do algorytmów jest za trudne.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # euqinu 2012-01-19 16:55
krótkie i konkretne
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Piroman 2012-09-12 17:38
Ten stos cyferek i literek w końcu ma jakiś sens! Dzięki ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+4 # mat021 2013-06-19 18:31
pomogło zrozumieć
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+4 # Marek2015 2015-01-29 13:47
Rewelacja, dziękuję!
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz