可以编写斐波那契函数以在 O(1) 时间内执行吗? [英] Can a Fibonacci function be written to execute in O(1) time?
问题描述
所以，我们看到了很多斐波那契问题.我个人讨厌他们.很多.不止很多.我认为如果我们可以让任何人都无法再次将其用作面试问题，那就太好了.让我们看看如何接近 O(1) 我们可以得到斐波那契.
So, we see a lot of fibonacci questions. I, personally, hate them. A lot. More than a lot. I thought it'd be neat if maybe we could make it impossible for anyone to ever use it as an interview question again. Let's see how close to O(1) we can get fibonacci.
这是我的开场白，几乎是从维基百科抄来的，当然还有足够的空间.重要的是，这个解决方案对于任何特别大的 fib 都会引爆，并且它包含对幂函数的相对幼稚的使用，如果你的库不好，它在最坏的情况下将其置于 O(log(n)).我怀疑我们可以摆脱幂函数，或者至少专门化它.有人来帮忙吗?除了使用查找表的有限*解决方案之外，是否存在真正的 O(1) 解决方案?
Here's my kick off, pretty much crib'd from Wikipedia, with of course plenty of headroom. Importantly, this solution will detonate for any particularly large fib, and it contains a relatively naive use of the power function, which places it at O(log(n)) at worst, if your libraries aren't good. I suspect we can get rid of the power function, or at least specialize it. Anyone up for helping? Is there a true O(1) solution, other than the finite* solution of using a look-up table?
#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);
}
*我知道，我知道，对于斐波那契的任何零实际用途来说，这已经足够了.
*I know, I know, it's enough for any of the zero practical uses fibonacci has.
推荐答案
给定任意大的输入，简单地读取 n 需要 O(log n)，因此从这个意义上说，不可能有恒定时间算法.因此，使用封闭形式的解决方案，或预先计算您关心的值，以获得合理的性能.
Given arbitrary large inputs, simply reading in n takes O(log n), so in that sense no constant time algorithm is possible. So, use the closed form solution, or precompute the values you care about, to get reasonable performance.
在评论中指出它实际上更糟，因为斐波那契是 O(phi^n) 打印斐波那契的 result 是 O(log (phi^n)) 即 O(n)!
In comments it was pointed out that it is actually worse, because fibonacci is O(phi^n) printing the result of Fibonacci is O(log (phi^n)) which is O(n)!
这篇关于可以编写斐波那契函数以在 O(1) 时间内执行吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
