Goldener Schnitt oder Pi in der Laufzeit

Es gibt viele Stellen, an denen die Zahlen und angezeigt werden. Ich bin gespannt auf Algorithmen, deren Laufzeit den goldenen Schnitt oder im Exponenten enthält.$\pi$$(1+\sqrt5)/2$$\pi$

Es ist eher die Basis als der Exponent, aber es ist eine FPT-Zeit eingebunden$O(\varphi^k n^2)$

" Ein effizienter Algorithmus mit fester Parameterverfolgung für die einseitige Kreuzungsminimierung ", Vida Dujmovic, Sue Whitesides, Algorithmica 40: 15–31, 2004.

Es ist auch eher eine Untergrenze als eine Obergrenze, aber:

„ Ein niedriger auf der Zeit gebunden durch ein Band einer Warteschlange oder zwei Pushdown- speichern zu simulieren$n^{1.618}$ “, Paul MB Vitányi, Inf. Proc. Lette. 21: 147–152, 1985.

Schließlich hat der Schinkensandwichbaum, eine inzwischen veraltete Datenstruktur in der Berechnungsgeometrie für Dreiecksbereichsabfragen, die Abfragezeit . Der goldene Schnitt liegt also korrekterweise im Exponenten, jedoch mit einem Protokoll und nicht als solches. Die Datenstruktur ist eine hierarchische Unterteilung der Ebene in konvexe Zellen mit der Gesamtstruktur eines Binärbaums, wobei jede Zelle und ihre Geschwister im Baum mit einem Schinken-Sandwich-Schnitt unterteilt sind. Die Abfragezeit wird durch die Wiederholung Q ( n ) = Q $O(n^{\log_2\varphi})\approx O(n^{0.695})$, welches die obige Lösung hat. Es wird (mit einem langweiligeren Namen) von beschrieben$Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$

" Halfplanar im linearen Raum und Suchbereich Abfragezeit$O(n^{0.695})$ , Herbert Edelsbrunner, Emo Welzl" Inf. Proc. Lette. 23: 289–293, 1986.

(aus meinem Kommentar oben)

Die Fortnow- und Melkebeek- Zeit / Raum-Untergrenze für die SAT-Lösbarkeit ( Zeit und n o ( 1 ) Raum) enthielt den goldenen Schnitt im Exponenten; aber es wurde später von Ryan Williams verbessert .$n^{\phi - \epsilon}$$n^{o(1)}$

Auch in der Basis und nicht im Exponenten: Der Monien-Speckenmeyer-Algorithmus für 3-SAT hat eine Laufzeit von . Dies war die erste nicht triviale Obergrenze für 3-SAT.$\varphi^n\cdot O(n)$

Ein weiteres Beispiel für in der Basis ist ein Algorithmus von Andreas Björklund und Thore Husfeldt zur Berechnung der Parität der Anzahl gerichteter Hamilton-Zyklen, die in der Zeit O ( φ n ) abläuft .$\varphi$$O(\varphi^n)$

http://arxiv.org/abs/1301.7250

Ebenfalls in der Basis: Der Lösch-Kontraktions-Algorithmus (Zykov, 1949) zur Berechnung der Anzahl der Graphenfärbungen läuft in der Zeit . Dies ist ein sehr kanonisches Beispiel dafür, wie der goldene Schnitt aus einer Fibonacci-Wiederholung für die Laufzeit der Bewertung einer natürlichen rekursiven Formel hervorgeht. Ich bin sicher, es ist das älteste.$O(\phi^{|E|+|V|})$

Mikko Koivisto fand einen Algorithmus zur Berechnung der Anzahl perfekter Übereinstimmungen (IWPEC 2009).$O(\phi^{|V|})$

Goldene Ration in der Basis: Ein sehr neuer FPT - Algorithmus durch Kociumaka und Pilipczuk, Faster deter Feedback Vertex Sets berechnet eine FVS der Größe in O * ( ( 2 + φ ) k ) die Zeit. (Sie verbessert die dann ihren Algorithmus in der Zeit laufen O * ( 3.592 k$k$$O^*\left((2 + \phi)^k\right)$$O^*(3.592^k)$ .)

Martin Bergers Kommentar: Der alte euklidische GCD-Algorithmus läuft im ungünstigsten Fall auf zwei aufeinanderfolgenden Elementen aus der Fibonacci-Sequenz. Weitere Details auf Wikipedia, die auch besagt:

Dieser 1844 von Gabriel Lamé veröffentlichte Beweis ist der Beginn der rechnerischen Komplexitätstheorie [93] und zugleich die erste praktische Anwendung der Fibonacci-Zahlen. [91]

$O(\log(n))$

[1] Was ist die zeitliche Komplexität des Euklid-Algorithmus , math.se