Ackerman函数

Ackerman函数的反函数

用途

Ackerman函数

Ackerman函数定义如下：

n+1 当m=0时

akm(m,n) = akm(m-1,1) 当m≠0,n=0时

akm(m-1, akm(m,n-1)) 当m≠0,n≠0时

Ackerman函数的反函数

ackerman函数的反函数——α（x）增长极为缓慢。对于可以想象到的n，α（n）都是在5之内的

用途

并查集的“路径压缩”算法：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α（x）。对于可以想象到的n，α（n）都是在5之内的。