Итак, мы видим много вопросов о фибоначчи. Я лично их ненавижу. Много. Больше, чем много. Я думал, что это будет аккуратно, если, возможно, мы сможем сделать невозможным когда-либо использовать его снова как вопрос интервью. Посмотрим, как близко к O (1) мы можем получить фибоначчи.
Здесь мой удар, довольно много извинился из Википедии, с, конечно, большим запасом. Важно отметить, что это решение будет взорваться для любого особо большого фига, и оно содержит относительно наивное использование силовой функции, которая в худшем случае помещает ее в O (log (n)), если ваши библиотеки не очень хороши. Я подозреваю, что мы можем избавиться от силовой функции или хотя бы специализировать ее. Кто-нибудь за помощь? Существует ли истинное решение O (1), отличное от конечного * решения использования справочной таблицы?
#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.
int main()
{
int target = 10;
cin >> target;
// should be close enough for anything that won't make us explode anyway.
float mangle = 2.23607610;
float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);
}
* Я знаю, я знаю, этого достаточно для любого из нулевых практических применений, связанных с фибоначчи.
Учитывая произвольные большие входы, просто чтение в n принимает O (log n), поэтому в этом смысле не существует алгоритма постоянного времени. Таким образом, используйте закрытое решение формы или предопределите ценности, которые вам нужны, чтобы получить разумную производительность.
Изменить: в комментариях было указано, что на самом деле это хуже, потому что фибоначчи O(phi^n) печатает результат Фибоначчи O(log (phi^n)), который O(n)!
Вот приблизительное решение O(1) для термина последовательности Фибоначчи. По общему признанию, O(log n) в зависимости от реализации системы Math.pow(), но это Fibonacci без видимого цикла, если ваш интервьюер ищет это. ceil() был вызван точностью округления при больших значениях, возвращаемых .9 повторение.
Пример в JS:
function fib (n) {
var A=(1+Math.sqrt(5))/2,
B=(1-Math.sqrt(5))/2,
fib = (Math.pow(A,n) - Math.pow(B,n)) / Math.sqrt(5);
return Math.ceil(fib);
}
Следующий ответ выполняет в O (1), хотя я не уверен, соответствует ли он вам вопрос. Он называется Мета-программирование шаблонов.
#include <iostream>
using namespace std;
template <int N>
class Fibonacci
{
public:
enum {
value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value
};
};
template <>
class Fibonacci<0>
{
public:
enum {
value = 0
};
};
template <>
class Fibonacci<1>
{
public:
enum {
value = 1
};
};
int main()
{
cout << Fibonacci<50>::value << endl;
return 0;
}
В программировании: "Вывод алгоритмов" Энн Калдейлай расширяет решение линейной алгебры, чтобы получить (перевести и реорганизовать с языка программирования в этой книге):
template <typename Int_t> Int_t fib(Int_t n)
{
Int_t a = 0, b = 1, x = 0, y 1, t0, t1;
while (n != 0) {
switch(n % 2) {
case 1:
t0 = a * x + b * y;
t1 = b * x + a * y + b * y;
x = t0;
y = t1;
--n;
continue;
default:
t0 = a * a + b * b;
t1 = 2 * a * b + b * b;
a = t0;
b = t1;
n /= 2;
continue;
}
}
return x;
}
Это сложность O (log n). Это, конечно, не постоянное, но я думаю, что стоит добавить к обсуждению, особенно учитывая, что он использует относительно быстрые целые операции и не имеет возможности ошибки округления.
Да. Предварительно расчитайте значения и сохраните в массиве, затем используйте N для поиска.
Выберите какое-то самое большое значение для обработки. Для любого большего значения поднимите ошибку. Для любого меньшего значения, чем это, просто сохраните ответ с меньшим значением и продолжайте вычисление для "наибольшего" значения и верните сохраненное значение.
В конце концов, O(1) означает "постоянный", а не "быстрый". При таком методе все вычисления будут занимать одинаковое количество времени.
Фибоначчи в O (1) пространстве и времени (реализация Python):
PHI = (1 + sqrt(5)) / 2
def fib(n: int):
return int(PHI ** n / sqrt(5) + 0.5)