此斐波那契解的时间和 space 复杂度

Question

我正在阅读这篇关于 fib 解决方案的文章（很有帮助）：https://medium.com/@johanna.fulghum/write-the-fibonacci-sequence-in-every-computational-complexity-9adf5ef12775

但是她上次解决问题的时间和 space 复杂性是否有错字？

function fib(n, a = 0, b = 1){
  if (n > 0) {
    return fib(n - 1, b, a + b)
  }
  return a
}

她说'This tail recursive solution is constant O(n) time and constant O(n) space complexity. This can’t be beat'。她的意思是 O(1) 对吗？因为 O(n) 是线性的。另外，我知道它是 O(1) space，但有人可以解释为什么是 O(1) 时间吗？对我来说似乎是 O(n) 时间

Answer 1

是的，这是一个打字错误（或编辑错误），space 复杂度也取决于编译器优化，以确保确实不变 O(1)。

这段代码的复杂度是Theta(n)时间，space复杂度可能是Theta(n)或Theta(1)，这取决于编译器是否将尾递归优化为循环。如果确实优化了尾递归，那么代码基本等同于她的方案3.

function fibs(n){
  let [a, b] = [0, 1]
  while (n > 0){
    [a, b] = [b, a + b]
    n -= 1
  }
  return a
}

我也对This can’t be beat的说法表示担忧。
事实上，斐波那契有一个closed form formula，可以用O(logn)计算，假设乘法是在常数时间内完成的。¹

(1) 如果这个假设不成立，而你实际上也关心算术运算的复杂性，这会使答案复杂化。基本上，这意味着您的复杂性取决于输出的大小，输出的大小也会呈指数增长。因为这呈指数增长。由于它呈指数增长，你需要 O(log(result)) 位来表示它，然后你得到线性时间的下限，因为输出的大小本身在 n.

中是线性的

此斐波那契解的时间和 space 复杂度

Time and space complexity of this Fibonacci solution

fibonacci

time-complexity