ALG4
74 Rozdział 3. Analiza sprawności algorytmów
• funkcja d(n) musi spełniać następującą własność: d(xy)- d(x)d(y) (np. d(n)=ir spełnia tę własność, a d(n)=n-J już nie).
Pomimo tych ograniczeń okazuje się, iż bardzo duża klasa równań może być dzięki powyższym wzorom z łatwością rozwiązana. Spróbujmy dla przykładu skończyć zadanie dotyczące przeszukiwania binarnego. Jak pamiętamy, otrzymaliśmy wówczas następujące równania:
T(\) = 2,
T(n) — 2 + 7^-jj.
Patrząc na zestaw podanych powyżej wzorów widzimy, że nie jest on zgodny zc „wzorcem" podanym wcześniej. Nic nie stoi jednak na przeszkodzie, aby za pomocą prostego podstawienia doprowadzić do postaci, która będzie nas satysfakcjonowała:
U(n) = T(n)~] « f/(l) = 7'(l)-l = l,
7X«)-i = i + r(j) « /./(«) = +
Identyfikujemy wartości stałych: ci=l, h-2 i d(n)-l, co pozwala nam zauważyć, iż zachodzi przypadek trzeci: a=d(b). Poszukiwany wynik ma zatem postać:
U(n) E o(«loS:l log, n) = O(n0 log, n) = ćł(log, 17).
3.7.4.Zamiana dziedziny równania rekurencyjnego
Pewna grupa równań charakteryzuje się zdecydowanie nieprzyjemnym wyglądem i nijak nie odpowiada podanym uprzednio wzorom i metodom. Czasem jednak zwy kła zmiana dziedziny powoduje, iż rozwiązanie pojawia się niemal natychmiastowo. Przeanalizujmy następujący przykład:
an = 3*_, dla 77 > 1, a0 = 1.
Równanie nie jest zgodne z żadnym poznanym wcześniej schematem. Podstawmy jednak b„=\ogia„ i zlogarytmujmy obie strony równania:
log2«„ = log: (3^i),
Wyszukiwarka
Podobne podstrony:
ALG4 54 Rozdział 3. Analiza sprawności algorytmów Tematyką tego rozdziału jest tzw. złożoność oblic
ALG4 64 Rozdział 3. Analiza sprawności algorytmów3.4. Przykład 3: Wpadamy w pułapkę Zadania z dwóch
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
Alg0 60 Rozdział 3. Analiza sprawności algorytmów • Znak graficzny 3 należy czyta
ALG2 52 Rozdział 3. Analiza sprawności algorytmów Rys. 3 -
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else //element zost
ALG8 68 Rozdział 3. Analiza sprawności algorytmów3.6. Nowe zadanie: uprościć obliczenia! Nic sposób
ALG0 70 Rozdział 3. Analiza sprawności algorytmów Przykład: SRL=xn-3x„.i+2 x„ -2=0 daje
ALG2 72 Rozdział 3. Analiza sprawności algorytmówn o) = i, i = A + O, A = 1. Po t
ALG6 76 Rozdział 3. Analiza sprawności algorytmów Analogicznie dla 2 otrzymamy: Vn > 1, A(n,2) =
ALG8 78___Rozdział 3 Analiza sprawności algorytmówZad. 3-4 Proszę rozwiązać następujące równanie
ALG2 12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostsz
ALG3 Rozdział 3Analiza sprawności algorytmów Podstawowe kryteria pozwalające na wybór właściwego al
ALG8 58Rozdział 3. Analiza sprawności algorytmów konania programu zależy od danej wejściowej n? W l
ALG4 194 Rozdział 7. Algorytmy przeszukiwania • powinna być tatwo obliczalna, tak
12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszych
ET4 74 Rozdział 5. Rynek usług turystycznych Mechanizm ten wyraża zależności przyczynowo-skutkowe
ALG4 24 Rozdział 1. Zanim wystartujemy Aby zaradzić zaanonsowanym wyżej problemom, przyjęło się zwy
więcej podobnych podstron