ALG6
76 Rozdział 3. Analiza sprawności algorytmów
Analogicznie dla 2 otrzymamy:
Vn > 1, A(n,2) = A{A{n -1,2),1) = 2A(n-1,2). co z kolei pozwala nam napisać, że:
V«> 1. A(n,2) = 2".
Z samej definicji funkcji Ackermanna możemy wywnioskować, żc:
Vm > 1 A(n,3) = żl(żl(w - 1,3),2) = 2*"'u> oraz ,4(0,3) = 1.
Na bazie tych równań możliwe jest rekurencyjne udowodnienie, żc:
2
2 n
Vw>l, .4(«,3) - 2
Nieco gorsza sytuacja występuje w przypadku A(n,4), gdzie trudno jest podać „wzór ogólny”. Proponuję spojrzeć na kilka przykładów liczbowych:
|
zł(l,4) = |
2. |
|
.4(2,4) = |
22 =4. |
|
AOA) = |
21" = 65536. |
2 f65536
.4(4,4) - 2 1
Wyrażenie w formie liczbowej A(4,4) jest - co może będzie zbyt dyplomatycznym stwierdzeniem - niezbyt oczywiste, nieprawdaż? W przypadku funkcji Ackermanna trudno jest nawet nazwać jej klasę — stwierdzenie, że zachowuje się ona wykładniczo, może zabrzmieć jak kpina!
3.8. Zadania
Zad. 3-1
Proszę rozważyć problem prawdziwości lub fałszu poniższych równań: a) e 0(/73);
Wyszukiwarka
Podobne podstrony:
ALG6 56 Rozdział 3. Analiza sprawności algorytmów jest intuicyjnie bardzo proste, dalej będziemy uż
ALG6 66 Rozdział 3. Analiza sprawności algorytmów return pos; else //element zost
ALG4 54 Rozdział 3. Analiza sprawności algorytmów Tematyką tego rozdziału jest tzw. złożoność oblic
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 -
ALG4 64 Rozdział 3. Analiza sprawności algorytmów3.4. Przykład 3: Wpadamy w pułapkę Zadania z dwóch
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
ALG4 74 Rozdział 3. Analiza sprawności algorytmów • funkcja d(n) musi spełniać następującą własność
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
ALG6 86 Rozdział 4. Algorytmy sortowania zamiany sąsiadujących ze sobą elementów, a druga będzie wy
ALG6 176 Rozdział6. Derekursywacja
12 PrzedmowaRozdział 3 Analiza sprawności algorytmów Przegląd najpopularniejszych i najprostszych
ET6 76 Rozdział 5. Rynek usług turystycznych w bardziej szczegółowym ujęciu: od konkurencji doskona
więcej podobnych podstron