在我大学的离散数学课程中，老师向学生展示了阿克曼函数 http://en.wikipedia.org/wiki/Ackermann_function并指派学生在纸上开发该函数。
除了作为递归优化的基准之外，阿克曼函数还有任何实际用途吗？
是的。 （反）阿克曼函数出现在算法的复杂性分析中。当它出现时，这意味着你几乎可以忽略这个术语，因为它增长得很慢（很像 log(log ... log(n)...)），即 lg*(n)。例如：最小生成树 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.7632 (also here http://www.andreygoder.com/talks/mstackermann.pdf) and 不相交集 http://en.wikipedia.org/wiki/Disjoint-set_data_structure森林建设。
Also: 达文波特-辛泽尔序列 http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
