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) =	2^2 =4.
AOA) =	2^1" = 65536.

2 f65536

.4(4,4) - 2    ¹

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(/7³);