雙重指數函數
外觀
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Double_Exponential_Function.svg/320px-Double_Exponential_Function.svg.png)
雙重指數函數是指公式為的函數,是指數為另一個指數冪的指數冪,在x<0時,雙重指數函數接近1,但當x>0時,雙重指數函數成長速率比指數函數還要快。
例如a = b = 10時:
- f(−1) ≈ 1.26
- f(0) = 10
- f(1) = 1010
- f(2) = 10100 = 古高爾(googol)
- f(3) = 101000
- f(100) = 1010100 = 古戈爾普勒克斯(googolplex)
階乘的成長速度比指數函數還快,但比雙重指數函數慢很多。而迭代冪次和阿克曼函數的成長速度比雙重指數函數要快很多。
雙重指數數列
[編輯]以下是一些和雙重指數有關的數列:
Aho和Sloane發現有許多整數數列的每一項是前一項的平方再加上一個整數,這類的數列常常可以用最接近雙重指數數列的整數來表示,且雙重指數數列中間的指數為2[1]。若一整數數列的第n項和n的雙重指數成正比,Ionascu 及Stanica將這樣的整數數列稱為「幾乎雙重指數」(almost doubly-exponential),可以定義為雙重指數加上一常數後再取整數[2]。
- 其中E ≈ 1.264084735305302為Vardi常數。
- 其中A ≈ 1.306377883863為米爾斯常數。
應用
[編輯]演算法複雜度
[編輯]在計算複雜性理論中,有些演算法的時間複雜度是雙重指數,例如:
數論
[編輯]有些數論中的上限是雙重指數,例如有n個相異質數的奇完全數的上限為[4]:
自從Miller和Wheeler在1951年利用EDSAC找到79位數的質數之後.利用電腦找到的已知最大質數和年份之間的關係為雙重指數函數[5]。
參考資料
[編輯]- ^ Aho, A. V.; Sloane, N. J. A., Some doubly exponential sequences, Fibonacci Quarterly, 1973, 11: 429–437 [2013-01-22], (原始內容存檔於2021-05-06)
- ^ Ionascu, E.; Stanica, P., Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences, Acta Mathematica Universitatis Comenianae, 2004, LXXIII (1): 75–87.
- ^ Gruber, Hermann; Holzer, Markus. Finite Automata, Digraph Connectivity, and Regular Expression Size (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) 5126: 39–50. 2008 [2013-01-23]. doi:10.1007/978-3-540-70583-3_4. (原始內容存檔 (PDF)於2011-07-11).
- ^ Nielsen, Pace P., An upper bound for odd perfect numbers, INTEGERS: the Electronic Journal of Combinatorial Number Theory, 2003, 3: A14 [2013-01-23], (原始內容存檔於2017-03-21).
- ^ Miller, J. C. P.; Wheeler, D. J., Large prime numbers, Nature, 1951, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.