Podwójna funkcja wykładnicza - Double exponential function
Podwójna wykładnicza funkcja jest stała podniesiony do potęgi w funkcji wykładniczej . Ogólny wzór to (gdzie a >1 ib >1), który rośnie znacznie szybciej niż funkcja wykładnicza. Na przykład, jeśli a = b = 10:
- f (0) = 10
- f (1) = 10 10
- f (2) = 10 100 = googol
- f (3) = 10 1000
- f (100) = 10 10 100 = googolplex .
Silnia rosną szybciej niż funkcje wykładnicze, ale znacznie wolniej niż funkcje podwójnie wykładnicze. Jednak tetracja i funkcja Ackermanna rosną szybciej. Zobacz notację Big O dla porównania tempa wzrostu różnych funkcji.
Odwrotnością podwójnej funkcji wykładniczej jest podwójny logarytm ln(ln( x )).
Podwójnie wykładnicze sekwencje
Mówi się, że ciąg dodatnich liczb całkowitych (lub liczb rzeczywistych) ma podwójnie wykładniczą stopę wzrostu, jeśli funkcja podająca n- ty wyraz ciągu jest ograniczona powyżej i poniżej funkcji podwójnie wykładniczej n . Przykłady obejmują
- W Liczby Fermata
- Liczby pierwsze harmoniczne: Liczby pierwsze p , w których sekwencja 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/ p przekracza 0, 1, 2, 3, …Pierwsze cyfry, zaczynające się od 0, to 2, 5, 277, 5195977, ... (sekwencja A016088 w OEIS )
- Te numery Pokój Mersenne
- Elementy ciągu Sylwestra (sekwencja A000058 w OEIS )
- Liczba k- arnych funkcji logicznych :
- Liczby pierwsze 2, 11, 1361, ... (sekwencja A051254 w OEIS )
Aho i Sloane zaobserwowali, że w kilku ważnych ciągach liczb całkowitych każdy wyraz jest stałą plus kwadrat poprzedniego wyrazu. Pokazują, że takie ciągi można utworzyć przez zaokrąglenie do najbliższej liczby całkowitej wartości funkcji podwójnie wykładniczej o środkowym wykładniku 2. Ionaşcu i Stănică opisują pewne bardziej ogólne warunki wystarczające, aby ciąg był dołem ciągu podwójnie wykładniczego plus stała .
Aplikacje
Złożoność algorytmiczna
W teorii złożoności obliczeniowej niektóre algorytmy zajmują czas podwójnie wykładniczy:
- Każda procedura decyzyjna dla arytmetyki Presburgera wymaga co najmniej podwójnego czasu wykładniczego
- Obliczanie bazy Gröbnera nad polem. W najgorszym przypadku baza Gröbnera może mieć wiele elementów, które są podwójnie wykładnicze w liczbie zmiennych. Z drugiej strony, złożoność najgorszego przypadku algorytmów bazowych Gröbnera jest podwójnie wykładnicza pod względem liczby zmiennych, a także rozmiaru wpisu.
- Znalezienie pełnego zestawu unifikatorów asocjacyjno-przemiennych
- Zadowalający CTL + (czyli w rzeczywistości 2-EXPTIME -complete )
- Eliminacja kwantyfikatora na rzeczywistych ciałach zamkniętych zajmuje podwójnie wykładniczy czas (patrz Cylindryczny rozkład algebraiczny ).
- Obliczanie uzupełnieniem o wyrażenie regularne
W niektórych innych problemach związanych z projektowaniem i analizą algorytmów sekwencje podwójnie wykładnicze są stosowane w projektowaniu algorytmu, a nie w jego analizie. Przykładem jest algorytm Chana do obliczania wypukłych kadłubów , który wykonuje sekwencję obliczeń przy użyciu wartości testowych h i = 2 2 i (szacunki dla ostatecznej wielkości wyjściowej), biorąc czas O( n log h i ) dla każdej wartości testowej w sekwencji . Z powodu podwójnego wykładniczego wzrostu tych wartości testowych, czas dla każdego obliczenia w sekwencji rośnie pojedynczo wykładniczo w funkcji i , a całkowity czas jest zdominowany przez czas dla ostatniego kroku sekwencji. Zatem całkowity czas działania algorytmu wynosi O( n log h ), gdzie h jest rzeczywistym rozmiarem wyjścia.
Teoria liczb
Niektóre teoretyczne granice liczb są podwójnie wykładnicze. Wiadomo, że liczby nieparzyste doskonałe z n odrębnymi czynnikami pierwszymi to co najwyżej
wynik Nielsena (2003). Wielkość maksymalną w d -lattice Polytope z k ≥ 1 wewnętrzne punkty siatkowe jest najbardziej
wynik Pikhurko.
Największa znana liczba pierwsza w erze elektronicznej wzrosła mniej więcej podwójnej funkcji wykładniczej roku od Miller i Wheeler znalazł 79-cyfrowy prime na EDSAC 1 w 1951 roku.
Biologia teoretyczna
W dynamice populacji zakłada się czasami, że wzrost populacji ludzkiej jest podwójnie wykładniczy. Warfolomeyev i Gurevich eksperymentalnie pasują
gdzie N ( y ) to liczba ludności w milionach w roku y .
Fizyka
W oscylatora Toda modelu siebie pulsacji logarytm amplituda zmienia się wykładniczo wraz z upływem czasu (w przypadku dużych amplitudach), a tym samym zmienia się amplituda podwójnie wykładniczej funkcji czasu.
Zaobserwowano, że makrocząsteczki dendrytyczne rosną w sposób podwójnie wykładniczy.