Fibonacci数列的迭代解是否伪多项式时间复杂度？

Question

当我们使用迭代方法查找斐波那契数列中的第n个数字时，我们运行一个for循环(n-2)次。这意味着时间复杂度将是O(n)。这是否正确，或者它实际上会根据输入的位数而成为伪多项式，就像背包问题一样？

- Ayan Majumdar

Answer 1

这里，我假设Fib(n)是一个计算斐波那契数列的迭代程序。可能类似于以下内容：

def Fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a

在这个上下文中，“Fib(n)是伪多项式”意味着计算Fib受其参数n的多项式限制，但不受其参数大小log(n)的多项式函数限制。在这种情况下是正确的。

“Fib(n)是O(n)”是关于Fib运行时间与其参数值有关的陈述。有时候“n”的含义会有歧义，但在这里没有--它是Fib的输入，否则“n”将在原始语句中指代两个不同的事物。在这里是正确的（尽管请参见下面的技术侧注）。

“Fib是O(n)”是有歧义的。有些人会告诉你n明显是指参数，而有些人会告诉你n总是指参数的大小。事实上是有歧义的，如果在上下文中不清楚，应该说清楚自己的意思（或者如果你听到并感到困惑，可以问一下它的意思）。一个不含糊的上下文是当你谈论P/NP问题类时--在那里，通常认为复杂度总是相对于输入的大小。

一个技术侧注：

迭代版本的Fib(n)执行O(n)算术操作，但它是否是O(n)时间取决于你的计算模型，具体来说，它是否能在O(1)时间内执行任意整数算术操作。个人而言，我会小心地说“Fib(n)执行O(n)算术操作”，而不是“Fib(n)是O(n)”--如果你绘制Fib(n)的运行时间曲线，你会发现它在实践中并不是线性时间，因为真正的大数实现肯定不是所有基本操作都是O(1)。

- Paul Hankin

---

嗨，保罗，谢谢你的回复。实际上我是算法方面的新手，不太理解P/NP等概念。我只是在参加一个MOOC课程，在那里他们教授了背包问题，并说对于背包重量W输入和n为物品数量，复杂度看起来像O(nW)。然而对于W来说，它实际上是伪多项式，因为它取决于输入的大小。这就是为什么我认为如果Fib迭代版本类似于背包问题，我们也需要输入n，即我们要找到的第n个Fib数。这里是否也会因为相同的原因像背包问题一样成为伪多项式？ - Ayan Majumdar

是的，从技术上讲，说它是伪多项式是正确的。 - Paul Hankin

严格来讲，大O符号应该基于输入大小计算。按照这个标准，迭代的斐波那契算法是伪多项式时间复杂度，因为它不是基于其输入大小的线性时间复杂度。实际上，这意味着如果你计算fib(10000)，你会需要一个非常大的数字，然后数据会溢出。 - AminM

Answer 2

是的，它实际上是O(n)。背包问题的时间复杂度非常奇怪，是一个例外。

- DollarAkshay

---

那就是我不明白的地方。为什么以及它是如何成为异常情况的？我对算法很新... - Ayan Majumdar