记忆斐波那契的时间复杂度？

Question

我有记忆斐波那契代码，但我无法弄清楚它的时间复杂度：

function fibMemo(index, cache) {
  cache = cache || [];
  if (cache[index]) return cache[index];
  else {
    if (index < 3) return 1;
    else {
      cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
    }
  }

  return cache[index];
}

这个函数的时间复杂度是多少？

Answer 1

取决于你的意思。

假设记忆正确完成，"operations" 的数量将是生成的数字数量。这意味着函数运行时间的增长与您尝试生成的数字数量有关。

所以它将是 O(n)，其中 n 是生成的数字的数量。

Answer 2

假设T(n)是n的时间复杂度，所以T(n) = T(n-1) + T(n-2)。因为我们计算F(n - 1)的时候F(n-2)在cache，所以F(n-2)的操作是1（从cache读），所以T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(n-n) + n .而 T(0) 是 1，所以 T(n) = O(n + 1) = O(n).

Answer 3

没有记忆

我认为当您不使用记忆时，在脑海中想象一下调用树的样子会很有帮助。例如，这是 fib(5):

的样子

这个算法的时间复杂度是多少？那么，我们调用了多少次 fib()？要回答这个问题，请考虑树的每一层。

第一关有一个电话：fib(5)。下一级有两个调用：fib(4) 和 fib(3)。下一层有四个。等等等等。每个节点都分支成两个额外的节点，因此它是 2*2*2... = 2^n。好吧，它是 O(2^n)，通常不完全是 2^n。可以看到这里level 4少了一个节点，level 5只有一个节点。

带记忆功能

现在想想记忆化会是什么样子。当您使用记忆时，您会记住您之前计算的结果。所以它看起来像这样：

周围有方块的只是返回记忆的结果。如果您忽略它们，您会看到该算法仅针对从 0 到 n.

的每个值调用一次

嗯，fib(1) 确实被称为“额外”一次，但由于我们在这里考虑 big-O，所以它不会改变任何事情。与周围有方块的呼叫相同。即使我们想包括它们，它仍然是 O(n).

为了向自己证明这一点并使其直观，请尝试为大于 fib(5) 的对象编写一个调用树。也许 fib(10) 或 fib(20)。你会发现，如果你眯起眼睛，它基本上是一条向下和向左移动的对角线。可能会有一些额外的分支在这里和那里发芽，但基本上，它是一条线。

记忆斐波那契的时间复杂度？

Time Complexity of Memoization Fibonacci?

javascript

big-o

runtime

fibonacci

time-complexity