当我对自己思考的时候,我正在阅读有关Haskell的教程. Haskell的tail函数有什么时间复杂度(以及为什么)?(在任何文档中都找不到答案)
I was reading a tutorial on Haskell when I thought to myself; what time complexity does Haskell's tail function have (and why)? (I cannot find an answer in any documentation)
我猜想对于大小为n的列表,tail函数将为 O(n),即仅将尾部复制到新列表并返回该列表.但是话又说回来,我对Haskell的基础体系结构了解不多(我是该语言的新手).
I would guess that for a list of size n, the tail function would be O(n), i.e just copying over the tail to a new list and returning that one. But then again, I do not know too much about the underlying architecture of Haskell (I'm new to the language).
当然,我可以安排时间.但是我还不知道如何在Haskell中计时,我还想了解Haskell如何处理该问题,以证明为什么是O(n)/O(1)或其他.
Of course, I could time it. But I don't know how to time stuff in Haskell yet, and I also want to learn how Haskell handles the problem, to justify why it is O(n)/O(1) or whatever.
先谢谢您了:)
推荐答案语言未指定的Haskell.但是在GHC(最常用的实现)中,它是O(1).尾部不需要复制-可以安全地在原始列表和仅使用列表尾部的任何人之间共享-因为Haskell中的所有内容都是不可变的.
Haskell the language doesn't specify. But in GHC (the most frequently used implementation), it is O(1). The tail does not need to be copied -- it is safe to share between the original list and whoever uses just the tail of the list -- because everything in Haskell is immutable.
挑战性问题:为什么保留列表中除 last 元素之外的所有元素的init在O(n)中运行?为什么上面的共享参数不适用于那里?
Challenge problem: why does init, which keeps all but the last element of a list, run in O(n)? Why doesn't the sharing argument above apply there?
更多推荐
Haskell的“尾部"函数具有什么时间复杂度?
发布评论