ALG1
3.2. Przykład 1: Jeszcze raz funkcja silnia... 61
W obliczeniach wykonywanych przez programistów zdecydowanie króluje podstawa 2, bowiem jest wygodnie zakładać, że np. rozmiar tablicy jest wielokrotnością liczby 2 etc.
Następnie na podstawie takich założeń częstokroć wyliczana jest złożoność praktyczna i z niej dedukowana jego klasa, czyli funkcja O. Ktoś o bardzo radykalnym podejściu do wszelkich „sztucznych” założeń, mających ułatwić wy liczenie pewnych normalnie skomplikowanych zagadnień, mógłby zakwestionować przyjmowanie podstawy 2 za punkt odniesienia, zapytując się przykładowa „a dlaczego nie 2,5 lub 2”? Pozornie takie postawienie sprawy wydaje się słuszne, ale na szczęście tylko pozornie! Na podstawie bowiem zacytowanego wyżej wzoru możemy z łatwością zauważyć, że logarytmy o odmiennych podstawach różnią się pomiędzy sobą tylko pewnym współczynnikiem stałym, który zostanie „pochłonięty” przez O na podstawie własności
c-0(f(nj) = 0{f(n))
Z tego właśnie względu w literaturze mówi się, że „algorytm Ac()(log A')”, a nic e O(log:A0”
Popatrzmy jeszcze na inny aspekt stosowania 0-notacji. Załóżmy, że pewien algorytm A został wykonany w' dwóch wersjach IVI i IV2. charakteryzujących się złożonością praktyczną odpowiednio 100 log:,V i I0N. Na podstawie uprzednio poznanych własności możemy szybko określić, że Wie OOogAO, W2 e 0(N)y czyli W1 jest lepszy od W2. Niestety', ktoś szczególnie złośliwy mógłby się uprzeć, że jednak algorytm W2 jest lepszy, bowiem dla np. N=2 mamy !00\ag22> 10-2... Wobec takiego stwierdzenia nie należy wpadać w panikę, tylko w'ziąć do ręki odpowiednio duże N, dla którego algorytm WI okaże się jednak lepszy od W2\ Nie należy bowiem zapominać, że (9-notacja ma charakter asymptotyczny i jest prawdziwa dla „odpowiednio dużych wartości N".
3.3. Przykład 2: Zerowanie fragmentu tablicy
Rozwiążemy teraz następujący problem: jak wyzerować fragment tablicy (tzn. macierzy) poniżej przekątnej (wraz z nią)? Ideę przedstawia rysunek 3-1.
Wyszukiwarka
Podobne podstrony:
ALG9 59 3.2. Przykład 1: Jeszcze raz funkcja silnia... Tę poszukiwaną funkcję będziemy zwać złożono
6 3.2. Przykład 1: Jeszcze raz funkcja
Konsulat honorowy Funkcje konsularne mogą być wykonywane przez: 1. Konsulów
442 ZBIGNIEW GOLINSKI Dodać należy jeszcze jeden przykład, zbliżony w swej funkcji do poprzedniego.
120485660101873325392447506232 n 0;Q!^l£Śis!^cych Pos-a-cl_____ BOHATER jeszcze raz udaje się na
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
ALG1 6.3. Kilka przykładów derekursywacji algorytmów 171 Musimy przełożyć krążki z drążka oznaczone
higeina 21 Przykłady programu świetlnego dla kurcząt-brojlerów Wiek Godzin światła na
Image013 1P :; -70 Wychowanie jako zwalczanie zdrowych instynktów życiowych wtedy, te jeśli Kasia je
img027 (42) A teraz wysłuchaj jeszcze raz kwestii z dialogu wraz z tłumaczeniem, powtarzaj poszczegó
img087 01 djvu 86 giego Antosia ojciec nazywa się Rybicki, więc i on nazywa się Rybicki. Powiedz ty
więcej podobnych podstron