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

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

取决于你的意思。

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

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

Answer 2

无需记忆

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

fib(5)

的样子：

这个算法的时间复杂度是多少？好吧，我们打了多少次

fib()

？要回答这个问题，请考虑树的每一层。

第一层有一个电话：

fib(5)

。下一级有两个调用：

fib(4)

和

fib(3)

。下一级有四个。等等等等。每个节点都分支成两个额外的节点，所以它是

2*2*2... = 2^n

。嗯，是

O(2^n)

，通常不完全是

2^n

。您可以看到这里第 4 级缺少一个节点，而第 5 级只有一个节点。

具有记忆功能

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

周围有方块的那些只是返回记忆的结果。如果忽略它们，您可以看到算法仅针对从

0

到

n

的每个值调用一次。

好吧，

fib(1)

确实被称为“额外”一次，但由于我们在这里考虑的是大O，所以它不会改变事情。与周围方块的调用相同。即使我们想包括它们，它仍然是

O(n)

。

为了向自己证明这一点并使其直观，请尝试为大于

fib(5)

的内容编写调用树。也许

fib(10)

或

fib(20)

。如果你眯起眼睛，你会发现它基本上呈对角线的形式，向下和向左移动。可能会有一些额外的树枝到处长出来，但基本上，它是一条线。

Answer 3

假设

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 4

这个问题的答案实际上有点棘手，并不是大多数人所期望的。

当问到 fib(n) 中执行的操作次数时，确实是 O(n)，但实际运行时间并不是 O(n)。如果我们假设加法的时间复杂度不是恒定的，那么运行时间就变成了 O(n^2)。原因如下：

设 x = fib(n)。我们知道 fib(n) 随 n 的位数呈指数增长，因此 x 有 n 位。

在递归情况下：f(n - 1) + f(n - 2)，我们将两个数字相加，这两个数字都有 O(n) 位。

将所有内容放在一起，我们执行 O(n) 操作，每个操作需要 O(n) 时间，导致总运行时间为 O(n^2)。