Question

人人都能对Ackermann为何能行使。 http://en.wikipedia.org

Tarjan数据结构书的分析是直观的。

在导言中,我还研究了Algorithms的情况,但似乎过于严格,而且不感兴趣。

感谢你们的帮助!

Answer 1

Applied to Disjoint-set forests

http://en.wikipedia.org/wiki/Disjoint-set_data_ruct”rel=“noreferer”

(about find and union) These two techniques complement each other; applied together, the amortized time per operation is only O(α(n)), where α(n) is the inverse of the function f(n) = A(n,n), and A is the extremely quickly-growing Ackermann function. Since α(n) is the inverse of this function, α(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

So why Ackerman?

http://www.mec.ac.in/resources/notes/ds/kruskul.htm

The Function lg*n

Note that lg*n is a very slow growing function, much slower than lg n. In fact is slower than lg lg n, or any finite composition of lg n. It is the inverse of the function f(n) = 2 ^2^2^…^2, n times. For n >= 5, f(n) is greater than the number of atoms in the universe. Hence for all intents and purposes, the inverse of f(n) for any real life value of n, is constant. From an engineer’s point of view, Kruskal’s algorithm runs in O(e). Note of course that from a theoretician’s point of view, a true result of O(e) would still be a significant breakthrough. The whole picture is not complete because the actual best result shows that lg*n can be replaced by the inverse of A(p,n) where A is Ackermann’s function, a function that grows explosively. The inverse of Ackermann’s function is related to lg*n, and is a nicer result, but the proof is even harder.

Applied to Disjoint-set forests

So why Ackerman?

The Function lg*n

友情链接