当我在阅读 Haskell 教程时，我心里想； Haskell 的 tail 函数的时间复杂度是多少(以及为什么)？(我在任何文档中都找不到答案)
我猜想对于大小为 n 的列表，tail 函数将是 O(n)，即只需将尾部复制到新列表并返回那个。但话又说回来，我对 Haskell 的底层架构不太了解(我是这门语言的新手)。
当然，我可以安排时间。但我还不知道如何在 Haskell 中计时，我也想了解 Haskell 如何处理这个问题，以证明为什么它是 O(n)/O(1) 或其他什么。
提前致谢:)
最佳答案
Haskell 语言未指定。但在 GHC(最常用的实现)中，它是 O(1)。尾部不需要复制——在原始列表和仅使用列表尾部的人之间共享是安全的——因为 Haskell 中的所有内容都是不可变的。
挑战问题:为什么 init(保留列表中除 last 元素之外的所有元素)的运行时间为 O(n)？为什么上面的共享论点在那里不适用？
关于haskell - Haskell 的 "tail"函数的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45044244/