解决斐波那契数列中的递归问题
我不知道这个算法中的数学原理，需要一些帮助。
算法：
if n<2 then
return n
else return fibonacci(n-1) + fibonacci(n-2)
语句
n < 2 是 O(1)
时间 n >=2 的时间复杂度为 O(1)
返回 n 为 O(1) 时间n>=2是- 返回 fib(n-1) + fib(n-2) 为 -
且时间 n>=2 为 T(n-1) + T(n-2) +O(1)
总计：O(1) T(n -1) + T(n-2) + O(1)
T(n) = O(1) 如果 n < 2
T(n) = T(n-1) + T(n-2) + O(1) 如果 n>=2
I'm unaware of the mathematics in this algorithm and could use some help.
Algorithm:
if n<2 then
return n
else return fibonacci(n-1) + fibonacci(n-2)
Statement
n < 2 is O(1)
Time n >=2 is O(1)
Return n is O(1)
Time n>=2 is -
Return fib(n-1) + fib(n-2) is -
and time n>=2 is T(n-1) + T(n-2) +O(1)
Total: O(1) T(n-1) + T(n-2) + O(1)
T(n) = O(1) if n < 2
T(n) = T(n-1) + T(n-2) + O(1) if n>=2
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我想您应该注意到这个函数的递归关系非常熟悉。通过按名称查找，您可以准确了解这种非常熟悉的复发速度。
但是，如果您未能实现直观的飞跃，您可以尝试使用简化的问题来限制运行时。本质上，您可以以保证增加运行时间同时使其更简单的方式修改算法。然后你算出新算法的运行时间，这给你一个上限。
例如，这个算法需要更长的时间并且更容易分析：
I think you're supposed to notice that the recurrence relation for this function is awfully familiar. You can learn exactly how fast this awfully familiar recurrence grows by looking it up by name.
However, if you fail to make the intuitive leap, you can try to bound the runtime using a simplified problem. Essentially, you modify the algorithm in ways guaranteed to increase the runtime while making it simpler. Then you figure out the runtime of the new algorithm, which gives you an upper bound.
For example, this algorithm must take longer and is simpler to analyze:
通过归纳：如果对于所有
k，对于fib(k)的计算花费小于C*2^knfib(n)的计算，我们有足够大的
C（对于C > K/0.25代码>，如<代码>2^n > 1）。这证明了 T(n)T(n)T(n)C*2^n，即T(n) = O(2^n)。（这里
T(n)是计算fib(n)的时间，K是计算fib所需的常数时间(n)当fib(n-1)和fib(b-1)都[已经]计算出来时。）By induction: if calculation of
fib(k)takes less thanC*2^kfor allk < n, for the calculation tome offib(n)we've gotfor sufficiently big
C(forC > K/0.25, as2^n > 1). This proves thatT(n) < C*2^n, i.e.T(n) = O(2^n).(Here
T(n)is the time for calculation offib(n),Kis the constant time needed for calculatingfib(n)when bothfib(n-1)andfib(b-1)are [already] calculated.)您需要求解递推方程：
You need to solve the recurrence equation: