网站地图
zenghuilan.com
生活小窍门 解释生活中的一切名词
阿克曼函数 发布于:

阿克曼函数(Ackermann)是非原始递归函数的例子。它需要两个自然数作为输入值,输出一个自然数。它的输出值增长速度非常快,仅是对于(4,3)的输出已大得不能准确计算。

1920年代后期,数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼,当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年,阿克曼又独立想出了另一个递归却非原始递归的函数。[1]

他最初的念头是一个三个变量的函数A(m,n,p),使用康威链式箭号表示法是mnp。阿克曼证明了它是递归函数。希尔伯特在On the Infinite猜想这个函数不是原始递归函数。阿克曼在On Hilbert's Construction of the Real Numbers证明了这点。

后来Rózsa Péter和拉斐尔·米切尔·罗宾逊定义了一个类似的函数,但只用两个变量。

Ackermann函数定义如下: 若m=0,返回n+1。

若m>0且n=0,返回Ackermann(m-1,1)。

若m>0且n>0,返回Ackermann(m-1,Ackermann(m,n-1))。

从Ackermann函数的定义中可以看出,Ackermann函数可以看成关于n的一个函数序列,其中第0个函数返回n+1,而第m个函数则是将第m-1个函数对1迭代n+1遍。对较小的m,该函数为:

Ackermann(0,n)=n+1

Ackermann(1,n)=n+2

Ackermann(2,n)=2*n+3

Ackermann(3,n)=2^(n+3)-3

Ackermann(4,n)=2^2^2^……^2-3,乘幂中共有n+3个2。

当m≥4,Ackermann函数的增长快得惊人。Ackermann(4,0)=13,Ackermann(4,1)=65533,Ackermann(4,2)=2^65536-3有19729位,而Ackermann(4,3)则即使是位数也不易估计。Ackermann(5,0)=65533,Ackermann(5,1)=Ackermann(4,65533)……

单变量反Ackermann函数(简称反Ackermann函数)α(x)定义为最大的整数m使得Ackermann(m,m)≤x。从上面的讨论中可以看到,因为Ackermann函数的增长很快,所以其反函数α(x)的增长是非常慢的,对所有在实际问题中有意义的x,α(x)≤4,所以在算法时间复杂度分析等问题中,可以把α(x)看成常数。

α(x)出现在使用了按秩合并和路径压缩的并查集算法的时间复杂度中。

int ack(int m,int n){

while(m!=0){

if( n==0) n=1;

else{

n=ack(m, n-1);}

m--;

}

return n+1;

}

int Ackermann(int m,int n)

{

int akm[m][n];

int i,j;

memset(akm,o,sizeof(akm));

for(j=0;j<n;j++)

akm[0][j]=j+1;

for(i=1;i<m;i++)

{

akm[0]=akm[i-1][1];

for(j=1;j<n;j++)

{

akm[j]=akm[i-1][akm[j-1]];

}

}

return akm[m][n];

}

stack s;

int ack(int m,int n)

{

int top=0;

s[top].mval=m;

s[top].nval=n;

do

{

while(s[top].mval)

{

while(s[top].nval)

{

top++;

s[top].mval=s[top-1].mval;

s[top].nval=s[top-1].nval-1;

}

s[top].mval--;

s[top].nval=1;

}

if(top>0)

{

top--;

s[top].mval--;

s[top].nval=s[top+1].nval+1;

}

}while(top!=0||s[top].mval!=0);

ack=s[top].nval+1;

top--;

}


相关文章推荐:
原始递归函数 | 大卫·希尔伯特 | 威廉·阿克曼 | 康威链式箭号表示法 | 递归函数 | 原始递归函数 | Ackermann函数 | 变量 | 时间复杂度 | 并查集 | 时间复杂度 |