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:***** / 121
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
+7 # student 2009-10-03 15:06
Wielki dzięki za art. Przyda się na kolokwium !
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+4 # + 2010-08-06 13:51
wykresy na duży plus.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+7 # 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
+6 # kt1117 2011-09-09 20:30
Zgadzam się z tym, że wprowadzenie do algorytmów jest za trudne.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # 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
+1 # inf 2016-06-14 12:21
Świetna robota, dzięki za zrozumienie tematu :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Andzioszek 2017-03-04 20:11
ten artykuł jest prawie idealny brakuje tu złożoności małe o i omega
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Bartek71 2017-06-13 20:37
Dzięki! Jedyne rysunki w sieci chyba. Od razu czaję !
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz