Złoty współczynnik lub Pi w czasie wykonywania

Istnieje wiele miejsc, w których pojawiają się liczby i . Ciekawi mnie algorytmy, których czas działania zawiera złoty współczynnik lub w wykładniku.$\pi$$(1+\sqrt5)/2$$\pi$

Jest to podstawa, a nie wykładnik, ale wiąże się czas $O(\varphi^k n^2)$ FPT

„ Efektywny algorytm ustalonego parametru dla minimalizacji jednostronnego skrzyżowania ”, Vida Dujmovic, Sue Whitesides, Algorytmica 40: 15–31, 2004.

Ponadto jest to dolna granica, a nie górna granica, ale:

„ An dolnej granicy czasu na symulację jednej kolejki lub dwóch sklepów pushdown za pomocą jednej taśmy$n^{1.618}$ ”, Paul MB Vitányi, Inf. Proc. Łotysz. 21: 147–152, 1985.

Wreszcie ten, który próbowałem znaleźć, kiedy natknąłem się na te dwa pozostałe: drzewo kanapkowe szynki, obecnie przestarzała struktura danych w geometrii obliczeniowej dla zapytań o zakresie trójkątnym, ma czas zapytania . Tak więc złoty współczynnik znajduje się w wykładniku, ale z logiem, a nie jako samym. Struktura danych jest hierarchicznym podziałem płaszczyzny na wypukłe komórki, z ogólną strukturą drzewa binarnego, gdzie każda komórka i jej rodzeństwo w drzewie są podzielone nacięciem kanapki z szynką. Czas zapytania zależy od powtarzalności Q ( n ) = Q $O(n^{\log_2\varphi})\approx O(n^{0.695})$, który ma powyższe rozwiązanie. Jest opisany (bardziej nudną nazwą) przez$Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$

„ Wyszukiwanie zakresu półpłaszczyznowego w przestrzeni liniowej i czas zapytania $O(n^{0.695})$ ”, Herbert Edelsbrunner, Emo Welzl, Inf. Proc. Łotysz. 23: 289–293, 1986.

(z mojego komentarza powyżej)

Fortnow i Melkebeek czasowego / przestrzenno-niższy związany na SAT rozwiązywalności ( czasu i n O ( 1 ), przestrzeń) zawierały stosunek złocisty wykładnika; ale został poprawiony później przez Ryana Williamsa .$n^{\phi - \epsilon}$$n^{o(1)}$

Również w bazie, a nie wykładniku: algorytm Monien-Speckenmeyer dla 3-SAT ma czas działania . To była pierwsza nietrywialna górna granica dla 3-SAT.$\varphi^n\cdot O(n)$

Innym przykładem w bazie jest algorytm Andreasa Björklunda i Thore Husfeldta do obliczania parzystości liczby ukierunkowanych cykli hamiltonowskich, który działa w czasie O ( φ n ) .$\varphi$$O(\varphi^n)$

http://arxiv.org/abs/1301.7250

Również w bazie: Algorytm usuwania i kurczenia (Zykov, 1949) do obliczania liczby zabarwień wykresów działa w czasie . Jest to bardzo kanoniczny przykład tego, jak złoty współczynnik pojawia się z nawrotu Fibonacciego w czasie oceny naturalnej rekurencyjnej formuły; Jestem pewien, że to najstarszy.$O(\phi^{|E|+|V|})$

Mikko Koivisto znalazł algorytm do obliczania liczby idealnych dopasowań (IWPEC 2009).$O(\phi^{|V|})$

Złota racja w bazie: najnowszy algorytm FPT autorstwa Kociumaka i Pilipczuka, Szybszy deterministyczny zestaw wierzchołków sprzężenia zwrotnego oblicza FVS wielkości w czasie O ∗ ( ( 2 + ϕ ) k ) . (Następnie poprawiają algorytm, aby działał w czasie O ∗ ( 3,592 k ) .)$k$$O^*\left((2 + \phi)^k\right)$$O^*(3.592^k)$

rozwinąć komentarz Martina Bergersa: starożytny euklidesowy algorytm GCD działa w najgorszym przypadku na dwóch kolejnych elementach z sekwencji Fibonacciego. więcej informacji na temat wikipedii, która również stwierdza:

Dowód ten, opublikowany przez Gabriela Lamé w 1844 r., Stanowi początek teorii złożoności obliczeniowej [93], a także pierwszego praktycznego zastosowania liczb Fibonacciego [91].

technicznie algorytm GCD działa w czasie logarytmicznym ale złoty współczynnik pokazuje się w liczbie kroków algorytmu.$O(\log(n))$

[1] jaka jest złożoność czasowa algorytmu Euclids, math.se