Золотое сечение или пи во время работы

Есть много мест, где числа $\pi$ и $(1+\sqrt5)/2$появляются. Мне любопытно узнать об алгоритмах, время выполнения которых содержит золотое сечение или$\pi$в показателе степени.

Это скорее основание, чем показатель степени, но есть время FPT в$O(\varphi^k n^2)$

« Эффективный трактируемый алгоритм с фиксированными параметрами для минимизации одностороннего пересечения », Вида Дуймович, Сью Уайтсайдс, Algorithmica 40: 15–31, 2004.

Кроме того, это нижняя граница, а не верхняя граница, но:

« П 1,618 нижней границы времени для имитации одной очереди или два Pushdown магазина от одной ленты », Пол MB Vitányi, Inf. Proc. Lett. 21: 147–152, 1985.$n^{1.618}$

Наконец, тот, который я пытался найти, когда натолкнулся на эти два других: дерево сэндвича с ветчиной, устаревшая в настоящее время структура данных в вычислительной геометрии для запросов треугольного диапазона, имеет время запроса . Таким образом, золотое сечение правильно в показателе степени, но с бревном, а не с самим собой. Структура данных представляет собой иерархическое разбиение плоскости на выпуклые ячейки с общей структурой двоичного дерева, где каждая ячейка и ее одноуровневый элемент в дереве разделены срезами ветчины. Время запроса определяется повторением Q ( n ) = Q $O(n^{\log_2\varphi})\approx O(n^{0.695})$, что имеет вышеуказанное решение. Это описано (с более скучным названием)$Q(n)=Q(\frac{n}{2})+Q(\frac{n}{4})+O(\log n)$

« Полуплоскостной поиск в линейном пространстве и время запроса $O(n^{0.695})$ », Герберт Эдельсбруннер, Emo Welzl, Inf. Proc. Lett. 23: 289–293, 1986.

(из моего комментария выше)

Fortnow и Melkebeek время / пространство нижнего предела для SAT разрешимости ( времени и п O ( 1 ) пространство) содержал золотое сечение в показателе; но это было улучшено позже Райаном Уильямсом .$n^{\phi - \epsilon}$$n^{o(1)}$

Также в основе, а не в показателе степени: алгоритм Монена-Спекенмейера для 3-SAT имеет время работы . Это была первая нетривиальная верхняя граница для 3-SAT.$\varphi^n\cdot O(n)$

Еще один пример в базе является алгоритм Андреаса Бьёрклунда и Тора Хусфельдта для вычисления четности числа направленных гамильтоновых циклов, которое выполняется за время O ( φ n ) .$\varphi$$O(\varphi^n)$

http://arxiv.org/abs/1301.7250

Также в основе: Алгоритм удаления-сжатия (Зыков, 1949) для вычисления количества раскрасок графов, выполняемых за время . Это очень канонический пример того, как золотое сечение появляется из повторения Фибоначчи для времени вычисления естественной рекурсивной формулы; Я уверен, что это самый старый.$O(\phi^{|E|+|V|})$

Микко Койвисто нашел алгоритм для вычисления числа совершенных совпадений (IWPEC 2009).$O(\phi^{|V|})$

Золотое сечение в базе: очень недавний алгоритм FPT, разработанный Kociumaka и Pilipczuk. Более быстрый детерминистический набор вершин обратной связи вычисляет FVS размера за O ∗ ( ( 2 + ϕ ) k ) времени. (Затем они улучшают свой алгоритм для запуска во времени O ∗ ( 3.592 k ) .)$k$$O^*\left((2 + \phi)^k\right)$$O^*(3.592^k)$

подробнее о комментарии Мартина Бергерса: древний евклидов алгоритм GCD работает в худшем случае на двух последовательных элементах последовательности Фибоначчи. более подробную информацию о Википедии, в которой также говорится:

Это доказательство, опубликованное Габриэлем Ламе в 1844 году, представляет собой начало теории вычислительной сложности [93], а также первое практическое применение чисел Фибоначчи [91].

технически алгоритм GCD выполняется в логарифмическом времени но золотое сечение проявляется в количестве шагов алгоритма.$O(\log(n))$

[1] какова временная сложность алгоритма Евклида , math.se