algorithm - 是斐波那契数列伪多项式的迭代解吗？

Question

因此，当我们进行迭代求解以找到斐波那契数列中的第 n 个数时，我们将运行 for 循环 (n-2) 次。这意味着时间复杂度为 O(n)。这是正确的还是它实际上是伪多项式取决于输入的位数，很像背包问题？

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) is 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) 的运行时间，你会发现它在实践中不是线性时间，因为真正的 bignum 实现肯定不是所有基本操作的 O(1)。