自下而上方法（DP）中斐波那契数列的时间复杂度

Question

自底向上算法

a[0]=0,a[1]=1
integer fibo(n)
   if a[n]== null
       a[n] = fibo(n-1) + fibo(n-2)
   return a[n]

这个算法怎么有O(N)的时间限制

对于 5 它调用 8 次。 pass of fibnacci series in Bottom Up approach

fibo(5) 调用 8 次从上到下，还调用 8 次从底部到 return 顶部。所以我认为总通话是 8+8=16。所以我不清楚时间复杂度是O(N)。

我发现这里回答了许多类似的问题，但所有这些都与我无关兴趣。其中一些是：

Time Complexity of Fibonacci Series

Time Complexity of Fibonacci Algorithm

任何人都可以提供帮助 appreciated.Thanks

Answer 1

在回答有关时间复杂度的问题之前，有几件事要快速提及。这样做的原因是时间复杂度至少部分取决于这些答案。

首先，您的程序中似乎存在一个错误，因为您有一个数组 'a' 用于基本条件（Fibbinacci 数 0 和 1）和一些数组 'm' fibo 函数，但再也没有使用过。更重要的是，当你达到 n=1 或 n=0 时，你 return m[n] 的值是完全未知的。因此，我将假设算法重写如下：

a[0]=0,a[1]=1
integer fibo(n)
   if a[n]== null
       a[n] = fibo(n-1) + fibo(n-2)
   return a[n]

好的，第二个问题。假设 a 总是定义为至少 n+1 个整数。需要有足够的空间容纳传入的数据。这很重要，因为 c++ 将允许您覆盖 n+1^th 索引处的值。这是越界和错误的，但 C++ 不提供此类保护。作为程序员，您可以像这样验证边界条件。（我假设是 c++，因为这是用 c++ 标记的。代码看起来更像 python，它有自己的环绕索引。）

第三，假设您不为算法的每个运行从一个新数组 'a' 开始。这很重要，因为如果 a 存储已经计算的值，那么您将不必重新评估这些值，从而节省计算时间。节省时间是一件好事，即使它不会影响我计算时间复杂度的方式。

太棒了。让我们开始你的问题。让我们用下面的图片来回答它。当您在 n 处开始算法时，您将对 fibo(n-1) 和 fibo(n-2) 进行两次递归调用，但它们不会同时发生。相反，对 fibo(n-1) 的第一次调用发生并且必须在第二次调用 fibo(n-2) 开始之前完成 100%。该调用由从第 n^th 行的 n-1 到第 n-1^th 行的绿线表示。

现在，这些绿线适用于每次递归，直到您到达 fibo(1) 调用。该调用提前终止，因为 a[n] 不为空。最后，对 fibo(0) 的第二次调用被执行，它也提前终止，因为 a[n] 不为空。好了，第一组递归调用到此为止。

随着每次递归调用 returns，进行第二次调用（由橙色虚线表示），但 a[n] 不再为空，因此调用提前终止并且调用 return到下一层。

那么，我们来数一数通话次数吧。从n到1就是n-1次递归调用。最后还有一次对 fibo(0) 的额外调用，因此是 n 次递归调用。然后在向上的路上有 n-2 个提前终止的附加呼叫。因此，我们总共有 2n-2 次调用，时间复杂度为 O(n)。

当然，如果您先调用 fibo(k)，然后再调用 fibo(k+x)，您只需执行前 2 次调用，因为从 fibo(k) 往下的所有内容都是已知的。在初始投资之后，这是一笔可观的节省。有什么问题吗？

关于 O(2n)=O(n)，这是一个很好的跟进。大 O 复杂性规则说，当您比较效率时，我们对数量级感兴趣。因此，假设您正在查看 n=1000。 O(n)=1000，O(2n)=2000，但 O(n²)=1,000,000。 O(n) 或多或少与 O(2n) 相同，但如果将它们与 O(n²) 进行比较，则差异巨大。同样，如果 O(n+1)=1001 与 O(n) 没有太大区别。所以，一般来说，我们说领先项，等式中最重要的值才是重要的。我们对额外条款并不感兴趣。我们对特定系数并不真正感兴趣，因为它们不会真正影响结果。

如果您仍有疑问，请访问此站点以获取更多信息。 https://justin.abrah.ms/computer-science/big-o-notation-explained.html

自下而上方法（DP）中斐波那契数列的时间复杂度

Time Complexity of fibonacci series in Bottom Up approach(DP)

c++

algorithm

fibonacci

time-complexity