이중 지수 함수

단일 지수 함수(파란색 곡선)와 비교하여 이중 지수 함수(빨간색 곡선)입니다.

이중 지수 함수는 지수 함수의 거듭제곱으로 증가하는 상수입니다.일반식은 f $f(x)=a^{b^{x}}=a^{(b^{x})}$ $f(x)=a^{b^{x}}=a^{(b^{x})}$ $f(x)=a^{b^{x}}=a^{(b^{x})}$ b $f(x)=a^{b^{x}}=a^{(b^{x})}$ $f(x)=a^{b^{x}}=a^{(b^{x})}$ ( $f(x)=a^{b^{x}}=a^{(b^{x})}$ x $f(x)=a^{b^{x}}=a^{(b^{x})}$ ) { $displaystyle$ f $(x$ ) = $a^{b^{x$ }} $f(x)=a^{b^{x}}=a^{(b^{x})}$ = $a^{($ b $^{x}}}}$ 이며, 여기서 a>1 및 b>1은 지수함수보다 훨씬 빠르게 성장한다.예를 들어 a = b = 10인 경우:

f(0) = 10
f(1) = 10¹⁰
f(2) = 10¹⁰⁰ = 구골
f(3) = 10¹⁰⁰⁰
f(100) = 10^10¹⁰⁰ = googolplex.

인수는 지수 함수보다 더 빠르게 증가하지만 두 배의 지수 함수보다 훨씬 더 느리게 증가합니다.그러나 테트레이션과 애커만 함수는 더 빨리 성장합니다.다양한 함수의 증가율 비교는 빅 O 표기법을 참조하십시오.

이중 지수 함수의 역수는 이중 로그 로그(log(x))입니다.

이중 지수 시퀀스

양의 정수(또는 실수)의 수열은 수열의 n번째 항을 주는 함수가 $n$ 의 2배 지수 함수에 의해 위와 아래에 경계가 있을 경우 두 배의 지수 성장률을 갖는다고 한다. 예:

페르마 수 $F(m)=2^{2^{m}}+1$
고조파 소수:1/2 + 1/3 + 1/5 + 1/7 + θ + 1/p가 0, 1, 2, 3, …을 넘는 소수 p.
0으로 시작하는 첫 번째 숫자는 2, 5, 277, 5195977, ...입니다(OEIS의 시퀀스 A016088).
이중 메르센 수 $MM(p)=2^{2^{p}-1$
실베스터 수열의 요소(OEIS의 시퀀스 A000058) $s_{n}=\left\lfloor E^{2^{n+1}+{\frac {1}{2}}\right\loor$ 여기서 E 1 1.264084735305302는 바르디의 상수입니다(OEIS의 시퀀스 A076393).
k-aryBoolean 함수의 수: $2^{2^{k}$
소수 2, 11, 1361, ...(OEIS의 시퀀스 A051254) $a(n)=\left\lfloor A^{3^{n}}\rfloor$ 여기서 A ≈ 1.306377883863은 밀스의 상수이다.

Aho와 Sloane은 몇 가지 중요한 정수 수열에서 각 항은 상수 + 이전 항의 제곱이라는 것을 관찰했다.이러한 수열은 중간 지수 ^[1]2로 이중 지수 함수의 값을 가장 가까운 정수로 반올림함으로써 형성될 수 있음을 보여준다.이오나슈쿠와 스테니커에서는 수열이 이중 지수 수열과 상수의 ^[2]바닥이 될 수 있는 보다 일반적인 충분 조건을 설명한다.

적용들

알고리즘의 복잡성

계산 복잡도 이론에서 2-EXPTIME은 이중 지수 시간에 해결 가능한 결정 문제의 클래스입니다.이것은 지수 공간에서 교대 튜링 기계로 해결할 수 있는 결정 문제의 집합인 AEXPACE와 동일하며 EXPSPACE의 ^[3]상위 집합이다.EXPTIME에 없는 2-EXPTIME의 문제의 예로는 Presburger ^[4]산술의 스테이트먼트를 증명 또는 반증하는 문제가 있습니다.

알고리즘의 설계와 분석의 다른 문제에서는 알고리즘의 분석보다는 알고리즘의 설계 내에서 이중 지수 시퀀스가 사용됩니다.예를 들어, 볼록 선체를 계산하는 Chan의 알고리즘은 테스트_i 값 h^2ⁱ = 2(최종 출력 크기에 대한 계산)를 사용하여 시퀀스의 각 테스트 값에 대해 O(n_i log h)를 소요하는 일련의 계산을 수행합니다.이들 테스트 값의 2배의 지수적 성장에 의해 시퀀스 내의 각 연산 시간은 i의 함수로서 단일 지수적으로 증가하며, 총 시간은 시퀀스의 마지막 단계까지의 시간이 지배한다.따라서 알고리즘의 전체 시간은 O(n log h)입니다.여기서 h는 실제 ^[5]출력 크기입니다.

수론

일부 수의 이론적인 경계는 이중 지수입니다.Nielsen(2003)^[6]의 결과에 따라 n개의 서로 다른 소수 인자를 갖는 홀수 완전수는 $2^{4^{n}}$ $({$ 2 $^{4^{n$ 인 것으로 알려져 있다.

k ≤ 1 내부 격자점을 가진 d차원 정수 격자에서 폴리토프의 최대 부피는 최대

{{displaystyle k\cdot (8d)^{d}\cdot 15^{d\cdot 2^{2d+1}},

Pikhurko(2001)^[7]의 결과.

1951년 ^[8]밀러와 휠러가 EDSAC1에서 79자리 소수를 발견한 이후 전자시대의 가장 큰 소수는 대략 두 개의 지수함수로 성장했습니다.

이론생물학

인구 역학에서 인구 증가는 때때로 두 배의 기하급수적이어야 한다.바르폴로메예프와 구레비치는^[9] 실험적으로 적합하다

(\displaystyle N(y)=375.6\cdot 1.00185^{1.00737^{y-1000}},)

여기서 N(y)은 y년도의 인구(백만 단위)입니다.

물리

Toda 발진기 모델에서 진폭의 로그는 시간에 따라 기하급수적으로 변화하므로(^[10]큰 진폭의 경우), 진폭은 시간의 두 배 지수함수로 변화합니다.

수지상 고분자는 이중 지수 ^[11]방식으로 성장하는 것이 관찰되었다.

레퍼런스

^ 를 클릭합니다Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly, 11: 429–437.
^ 를 클릭합니다Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences" (PDF), Acta Mathematica Universitatis Comenianae, LXXIII (1): 75–87.
^ Christos Papadimitriou, 계산 복잡도(1994), ISBN 978-0-201-53082-7.섹션 20.1, 결론 3, 495페이지.
^ 피셔, M. J.와 마이클 O. 라빈, 1974년 "프레즈버거 산수의 초지수 복소수.2006년 9월 15일 응용수학 SIAM-AMS 심포지엄 'Wayback Machine'에서의 아카이브 Vol.7: 27-41
^ Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry, 16 (4): 361–368, doi:10.1007/BF02712873, MR 1414961
^ 를 클릭합니다Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.
^ Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika, 48 (1–2): 15–24, arXiv:math/0008028, Bibcode:2000math......8028P, doi:10.1112/s0025579300014339
^ 를 클릭합니다Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.
^ 를 클릭합니다Varfolomeyev, S. D.; Gurevich, K. G. (2001), "The hyperexponential growth of the human population on a macrohistorical scale", Journal of Theoretical Biology, 212 (3): 367–372, doi:10.1006/jtbi.2001.2384, PMID 11829357.
^ 를 클릭합니다Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A, 40 (9): 1–18, Bibcode:2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016.
^ Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society. 117 (8): 2159–2165. doi:10.1021/ja00113a005.

[1] 를 클릭합니다Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly, 11: 429–437.

[2] 를 클릭합니다Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences" (PDF), Acta Mathematica Universitatis Comenianae, LXXIII (1): 75–87.

[3] Christos Papadimitriou, 계산 복잡도(1994), ISBN 978-0-201-53082-7.섹션 20.1, 결론 3, 495페이지.

[4] 피셔, M. J.와 마이클 O. 라빈, 1974년 "프레즈버거 산수의 초지수 복소수.2006년 9월 15일 응용수학 SIAM-AMS 심포지엄 'Wayback Machine'에서의 아카이브 Vol.7: 27-41

[5] Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry, 16 (4): 361–368, doi:10.1007/BF02712873, MR 1414961

[6] 를 클릭합니다Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.

[7] Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika, 48 (1–2): 15–24, arXiv:math/0008028, Bibcode:2000math......8028P, doi:10.1112/s0025579300014339

[8] 를 클릭합니다Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.

[9] 를 클릭합니다Varfolomeyev, S. D.; Gurevich, K. G. (2001), "The hyperexponential growth of the human population on a macrohistorical scale", Journal of Theoretical Biology, 212 (3): 367–372, doi:10.1006/jtbi.2001.2384, PMID 11829357.

[kouz-10] 를 클릭합니다Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A, 40 (9): 1–18, Bibcode:2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016.

[11] Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society. 117 (8): 2159–2165. doi:10.1021/ja00113a005.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

이중 지수 함수

네임스페이스

더

목차

이중 지수 시퀀스

적용들

알고리즘의 복잡성

수론

이론생물학

물리

레퍼런스