Haskell 中的整数时间复杂度
上周我在学校接到了一项作业，要实现一个计算斐波那契数列中第 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"
我感谢
Viktor 的所有回答
I had an assignment in school last week to implement a function for calculating the n:th number in the fibonacci sequence. A 'sub-assignment' was to implement it using accumulation(Might not be a correct translation) in order to give the function O(n) time complexity. This all worked fine until I tried making the function (Int -> Integer). By experimenting a bit I realised that the time complexity was close to O(n^2) for really large numbers.
It occurs to me that this must be because of the Integer implementation, which makes me a bit curious about how it works. I did a few Google searches and didn't find anything that seemed useful so I am turning to you guys in hope of either getting an explanation or a link that explains it thoroughly.
My code:
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"
I am thankful for all answers
Viktor
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这实际上与 Haskell 无关，这只是斐波那契数快速呈指数增长这一事实的结果。具体来说，第 n 个斐波那契数大约有 (log2 φ) n 或大约 0.48 n 位，其中 φ 是黄金比例 (1 + sqrt 5) / 2。由于 k 位整数的加法需要 O (k) 时间，您的 O(n) 加法实际上总共需要 O(n^2) 时间，因为平均而言您要添加的数字有 O(n) 位。
（坚持者请注意：上面的大 O 应该是大 Theta。）
This has nothing to do with Haskell really, it's just a result of the fact that the Fibonacci numbers grow exponentially quickly. Specifically, the nth Fibonacci number has about (log2 φ) n or roughly 0.48 n bits where φ is the golden ratio (1 + sqrt 5) / 2. Since addition of k-bit integers takes O(k) time, your O(n) additions actually take a total of O(n^2) time, because on average the numbers you're adding have O(n) bits.
(Note for sticklers: big O should really be big Theta in the above.)
要添加到 Reid 的答案，您的算法具有 O( N）时间复杂度取决于您认为执行的步骤。这是对时间复杂度的一个常见误解：时间复杂度始终与执行时间相对应。
考虑什么步骤取决于我们想要分析问题的深度。如果您将一个步骤定义为整数的一次加法，是的，您的带有累加器的算法将在 O(N) 时间内运行。如果将一个步骤定义为单字加法（32 位或 64 位加法），则其运行时间为 O(N^2)，正如 Reid 所解释的那样。
如果您希望复杂性分析与执行时间相对应，则需要使用执行时间受常量限制的执行步骤，例如两个处理器字的相加。整数的加法则不然，因为整数可以任意大。
To add to Reid's answer, the fact that your algorithm has O(N) time complexity depends on what you consider to be the step of execution. This is a common misconception of time complexity: that time complexity always corresponds to execution time.
What to consider the step depends on how deep we want to analyse the issue. If you define a step as one addition of Integer, yes, your algorithm with accumulators runs in O(N) time. If you define a step as one word addition (a 32- or 64-bit addition), it runs in O(N^2) as Reid explained.
If you want your complexity analysis to correspond to the execution time you need to use a step of execution whose execution time is bounded above by a constant, like the addition of two processor words. Addition of Integers is not, because Integers can be arbitrarily large.