ackerman函式

是一種函式，功能是比較它們趨向無窮的快慢。

基本介紹

• 中文名：阿克曼函式
• 外文名：ackerman函式
• 名稱：雙遞歸函式
• 使用：洛必達法則
• 作用：比較它們趨向無窮的快慢
• 領域：高級程式設計語言逆返調用

基本信息

當一個函式及它的一個變數是由函式自身定義時，稱這個函式是雙遞歸函式.當兩個連續函式都趨於無窮時，我們常用洛必達法則來比較它們趨向無窮的快慢。函式的階越高，它趨向無窮的速度就越快。在定義在正整數域上的函式中，n!趨向於正無窮的速度非常快，所以在算法設計中如果出現這樣的時間複雜度就太糟糕了。logn趨向無窮的速度則非常慢。

今天你將看到一個增長速度比n!快的多的函式和一個比logn慢的多的函式，它們都源於一個函式–’Ackerman Function’。

並非一切的遞歸函式都有通項公式，Ackerman函式就是這么一個例子。它是一個雙遞歸函式， Ackerman函式有A(n,m)有兩個獨立的整變數m>=0,n>=0，其定義如下

A(1,0)=2; (1)

A(0,m)=1 m>=0 (2)

A(n,0)=n+2, n>=2 (3)

A(n,m)=A(A(n-1,m),m-1) n,m>=1 (4)

（在不同參考資料上，上述定義式會有細微區別）

對任意自然數m，A(n,m)定義了關於n的一個單變數函式。遞歸式的第三式定義了函式“加2”。

m=1時,由於A(1,1)=A(A(0,1),0)=A(1,0)=2

以及A(n,1)=A(A(n-1),1),0)=A(n-1,1)+2(n>1)，因此A(n,1)=2n(n>=1)，即A(n,1)定義了函式“乘2”

m=2時，由於A(1,2)=A(A(0,2),1)=A(1,1)=2

A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，因此A(n,2)=2^n

以此類推，A(n,3)=2^(2^(2^…2)...)其中2的層數為n

A(n,4)的增長速度已經變得難以想像的快，以至於不能寫出一個通項公式來表示這一函式。

下面再來考慮單變數Ackerman函式A(n):=A(n,n)。 設其逆函式為B(n):=min{k|A(k)>=n}，即B(n)是使n<=A(k)成立的最小k值。

由A(0)=1,A(1)=2,A(2)=4,A(3)=16推知B(1)=0,B(2)=1,B(3)=B(4)=2和B(5)=…=B(16)=3。由此可以看出B(n)的增長速度非常慢。

A(4)=222…2其中2的層數為65535，這個數有log(A(4))位。所以，對於通常所見到的正整數n，有B(n)<=4

但是理論上B(n)沒有上界，隨著n的增加，它將以難以想像的慢速度趨向正無窮大。

ackerman函式的反函式——α（x）增長極為緩慢。對於可以想像到的n，α（n）都是在5之內的

用途

並查集的“路徑壓縮”算法：在集合的查找過程中順便將樹的深度降低。採用路徑壓縮後，每一次查詢所用的時間複雜度為增長極為緩慢的ackerman函式的反函式——α（x）。對於可以想像到的n，α（n）都是在5之內的。