Akermana funkcio: Malsamoj inter versioj
| [nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
Maksim (diskuto | kontribuoj) Nova paĝo: En matematiko, '''akermana funkcio''' aŭ '''funkcio de Ackermann-Péter''' estas funkcio ''A(m,n)'' kiu prenas du naturajn nombrojn kiel argumentoj kaj redona... |
Maksim (diskuto | kontribuoj) eNeniu resumo de redakto |
||
Linio 8:
n+1 & \mbox{ se } m = 0 \\
A(m-1, 1) & \mbox{ se } m > 0 \mbox{ kaj } n = 0 \\
A(m-1, A(m, n-1)) & \mbox{ se } m > 0 \mbox{ kaj } n > 0
\end{cases}
</math>
Linio 51:
: ''A(m, 0) = A(m-1, 1)'' respektivas al tio ke
: <math>2\uparrow^{m+1} 3=2\uparrow^m 4</math>
aŭ
: ''hyper(2, m+1, 3) = hyper(2, m, 4)''
Linio 204:
Kelkaj malmulte malsamaj difinoj de ''α(m, n)'' ekzistas; ekzemple, ''log<sub>2</sub> n'' estas iam anstataŭigita per ''n'', kaj la [[planka funkcio]] estas iam anstataŭigis per [[plafona funkcio]].
==
La akermana funkcio, pro ĝia difino kun de ege profunda rikuro, povas esti uzata por provi kiel bona estas la optimumigo de rikuro farata de iu kompililo.
Linio 212:
Rekta komputo de ''A(1, n)'' prenas [[lineara tempo|linearan tempon]] de ''n''. Rekta komputo de ''A(2, n)'' postulas [[kvadrata tempo|kvadratan tempon]], pro tio ke ĝi elvolviĝas al ''[[Granda O|O]](n)'' da nestitaj vokoj de ''A(1, k)'' por diversaj ''k''. Komputo de ''A(3, n)'' postulas tempon ''O(4<sup>n+1</sup>)''. La kalkulado de ''A(3, 1)'' en la ekzemplo pli supre prenas 16=4<sup>2</sup> paŝojn.
''A''(4, 2) ne povas esti komputita per simpla rikura laŭ la difino en taŭga daŭro. Anstataŭe, formuloj kiel ekzemple ''A(3, n) = 8×2<sup>n</sup>-3'' estas
== Vidu ankaŭ ==
* [[Granda O]]
| |||