哪些函數的增長速度能勝過指數函數？

01-11

指數級增長增長速度非常迅速，哪些函數相比指數函數更勝一籌？

可以把 Busy Beaver function 中的可計算性換成可定義性：「能用 n 個符號惟一定義的最大的自然數」。這是 Rayo 函數一個較為簡單的修改版。

$R(n)=sup{minmathbb{N} | exists phiinmathrm{Lang}_1^omega:mathrm{Godel}(phi)le nwedgemathrm{Unique}(phi)wedgephi(m)}$

其中 $mathrm{Lang}_1^omega$ 為允許任意有限階量化的、有一個自由變數的集合論語句組成的集，Unique 表示語句為一個數的定義（只有唯一數滿足它），Godel 為哥德爾編碼。

如果說 TREE 這種還能經過抽象想像一下它有多大的話，那麼 R(n) 真的，已經到了想像力的邊界了。

阿克曼函數

當年學習演算法的時候，有個數據結構叫disjoint set，為了證明這個演算法的複雜度，必須引入阿克曼函數。這個函數的反函數幾乎就是常數，可見其增長速度有多快

相信所有熟讀CLRS的人，都會知道這個函數的

$f(x)=int_0^x g(t) dt$ , 其中 $g(t)$ 滿足條件 $forall tin mathbb{R},g(t)>e^t$

Γ函數， $Gamma(s)=int_0^infty x^{s-1}e^x dx$

$f(x) =( (1-frac{1}{x^{K} } )^{x} )^{(K)} , xin left( -1,0 ight) , Kin Z_+, K is even$

If the domain of $f(x)$ "contains" interval $(t,infty ) , tin R$ ,then $f(x)$ cannot grow very fast whatever you define it and there exists a function $S(x), xin left( p , q ight) ,p,qin R$ ( such as $tan(x)$ ) "grows faster" than $f(x)$

tanx

比乘法更大的是乘方，比乘方更大的是什麼？

階乘函數。也就是gammar函數

bigfoot函數,超過rayo

正切，階乘

差不多吧歡迎補充

難道不是正切函數tan(x)？

$x!=int_0^infty t^xe^{-t}dt$

階乘，增長比指數函數快

請問n的n次方不是比n階乘增長快嗎？

阿克曼函數。它是定義運算的，從加法、乘法、乘方到超級冪……依次類推上去。

三角函數，例如正切：tan(x)

這個問題的答案一定首推伽馬函數啊。

Gamma(x) = int_0^infty t^{x-1} mathrm{e}^t ,mathrm{d}t

本質上就是階乘向實數域的推廣，最早的形式(跟現在不一樣)是歐拉大神為了推廣階乘構造的一個無窮乘積，後人把該函數自變數平移了1，就成了今天的伽馬函數，公式在手機上打的，不知對不對，待會兒檢查。

比較常見的有階乘；此外，限制在特定範圍的話，似乎可以根據初等函數的泰勒展開判斷增長速率的大小。

階乘函數

如果不是初等函數就太多了。

指數函數，a^x

指數函數多個方，a^(x^2)

指數的指數，a^(b^x)

=========神聖的分割線========

這種問題很無聊啊，不過既然寫都寫了，我就放個P吧！

有人指出之前的公式推導有誤，但x=0(即y縱軸)是否可以看做函數就不得而知了

說句體外話：x=0代表什麼嗎？你造嗎？

答不上來的立刻去翻初中數學書！

答閉