Да.Она называется Формула Бине , или, иногда, неправильно , Формула Де Мойр* открыть формулу Бине до Binet), и включает в себя золотое сечение Phi.Математическое обоснование этого (см. Ссылку) немного сложное, но выполнимое:
Хотя это приблизительная формула, числа Фибоначчи являются целыми числами -- поэтому, когда вы достигнете достаточно высокой точности (зависит от n ), вы можете просто приблизить число из формулы Бине к ближайшему целому числу.
Точность, однако, зависит от констант, так что выв основном есть две версии, одна с числами с плавающей запятой и одна с числами двойной точности, вторая также работает в постоянном времени, но немного медленнее.Для large n вам понадобится библиотека чисел произвольной точности , и у них есть время обработки, которое зависит от используемых чисел;как заметил @MattTimmermans, вы, вероятно, получите алгоритм O (log ^ 2 n).Это должно происходить при достаточно больших значениях n , чтобы вы застряли с библиотекой большого числа, несмотря ни на что (но мне нужно проверить это, чтобы убедиться).
В противном случае формула Бине в основном состоит из двух возведений в степень и одного деления (три суммы и деления на 2, вероятно, пренебрежимо малы), в то время как рекурсивная формула в основном использует вызовы функций, а итерационная формула использует цикл.В то время как первая формула O (1), а две другие O (n), фактическое время больше похоже на a , bn + c и dn + e, со значениями для a, b, c, d и e, которые зависят от аппаратного обеспечения, компилятора, реализации и т. Д.С современным процессором очень вероятно, что a не слишком больше, чем b или d , что означает, что формула O (1) должна быть быстрее дляпочти каждый n .Но большинство реализаций итеративного алгоритма начинаются с
if (n < 2) {
return n;
}
, что, скорее всего, будет быстрее при n = 0 и n = 1. Я уверен, что формула Бине быстрее для любого n, кроме одной цифры.