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

Question

我有memoization fibonacci代码,我无法弄清楚时间复杂性是什么:

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

取决于你的意思.

假设记忆正确完成,"操作"的数量将是生成的数字的数量.这意味着函数运行时会相对于您尝试生成的数字量而增长.

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

Answer 2

假设T(n)是 n 的时间复杂度，所以T(n) = T(n-1) + T(n-2)。因为F(n-2)是在cache我们计算的时候F(n - 1)，所以 的运算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。您可以在此处看到第 4 级缺少一个节点而第 5 级只有一个节点。

带记忆功能

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

周围有正方形的那些只是返回记忆的结果。如果您忽略它们，您会看到该算法只为从0to 的每个值调用一次n。

好吧，fib(1)确实被称为“额外”一次，但既然我们在这里考虑的是大 O，它不会改变事情。与周围正方形的呼叫相同。即使我们想包括它们，它仍然是O(n).

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