5

上周我在学校有一个任务，要实现一个计算斐波那契数列中第 n 个数的函数。“子任务”是使用累积（可能不是正确的翻译）来实现它，以便给函数 O(n) 时间复杂度。在我尝试制作函数（Int -> Integer）之前，这一切都很好。通过一些实验，我意识到对于非常大的数字，时间复杂度接近 O(n^2)。我突然想到这一定是因为 Integer 的实现，这让我有点好奇它是如何工作的。我做了一些谷歌搜索，没有找到任何似乎有用的东西，所以我转向你们，希望得到一个解释或一个彻底解释它的链接。

我的代码：

ackfib 0 = 0
ackfib 1 = 1        
ackfib n = loop n 1 0 1
    where
        loop n n1 n2 i 
            | i < n     = loop n (n1+n2) n1 (i+1)
            | i == n    = n1
            | i > n     = error "n must be greater than or equal to 0"

我感谢所有的答案

维克多

4

2 回答 2

13

这实际上与 Haskell 无关，这只是斐波那契数以指数方式快速增长的结果。具体来说，第 n 个斐波那契数大约有 (log 2 φ) n 或大约 0.48 n 位，其中 φ 是黄金比例 (1 + sqrt 5) / 2。由于 k 位整数相加需要 O(k) 时间，因此您的 O (n) 加法实际上总共需要 O(n^2) 时间，因为平均而言，您要添加的数字有 O(n) 位。

（坚持者注意：上面的大 O 应该是大 Theta。）

于 2010-09-26T15:46:19.780 回答
7

为了补充Reid 的答案，您的算法具有 O(N) 时间复杂度的事实取决于您认为执行的步骤。这是对时间复杂度的一个常见误解：时间复杂度总是对应于执行时间。

考虑什么步骤取决于我们要分析问题的深度。如果您将步骤定义为整数的一个加法，是的，您的带有累加器的算法在 O(N) 时间内运行。如果您将一个步骤定义为一个单词加法（32 位或 64 位加法），它会在 O(N^2) 中运行，正如 Reid 解释的那样。

如果您希望您的复杂性分析与执行时间相对应，您需要使用一个执行步骤，其执行时间由一个常数限定，例如添加两个处理器字。整数的加法不是，因为整数可以任意大。

于 2010-09-26T15:56:55.220 回答