双重指数函数

双重指数函数是指公式为函数,是指数为另一个指数幂的指数,在x<0时,双重指数函数接近1,但当x>0时,双重指数函数成长速率比指数函数还要快。

双重指数函数(红色)和一般实数指数幂(蓝色)的比较

例如a = b = 10时:

阶乘的成长速度比指数函数还快,但比双重指数函数慢很多。而迭代幂次阿克曼函数的成长速度比双重指数函数要快很多。

双重指数数列

以下是一些和双重指数有关的数列:

 
 
 

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]

参考资料

  1. ^ Aho, A. V.; Sloane, N. J. A., Some doubly exponential sequences, Fibonacci Quarterly, 1973, 11: 429–437 [2013-01-22], (原始内容存档于2021-05-06) 
  2. ^ Ionascu, E.; Stanica, P., Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences, Acta Mathematica Universitatis Comenianae, 2004, LXXIII (1): 75–87 .
  3. ^ 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). 
  4. ^ 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) .
  5. ^ Miller, J. C. P.; Wheeler, D. J., Large prime numbers, Nature, 1951, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0 .