本文介绍了为什么计算斐波那契数列的复杂度是 2^n 而不是 n^2?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我试图使用递归树找出斐波那契数列的复杂度,并得出树的高度 = O(n) 最坏情况,每个级别的成本 = cn,因此complexity = n*n=n^2

I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n) worst case, cost of each level = cn, hence complexity = n*n=n^2

怎么是O(2^n)?

推荐答案

一个朴素的递归斐波那契数列的复杂度确实是 2ⁿ.

The complexity of a naive recursive fibonacci is indeed 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) =
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

在每个步骤中,您调用 T 两次,从而提供最终的渐近障碍:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

In each step you call T twice, thus will provide eventual asymptotic barrier of:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

奖励:斐波那契最好的理论实现实际上是一个闭合公式,使用黄金比例:

bonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio:

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(然而,由于浮点运算,它在现实生活中存在精度误差,不精确)

(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact)

这篇关于为什么计算斐波那契数列的复杂度是 2^n 而不是 n^2?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

06-23 23:16