哈斯克尔的“尾巴”函数有什么时间复杂性？
2019-07-24
当我想到自己时,我正在阅读关于
Haskell的教程;
Haskell的尾部函数具有什么时间复杂度(以及为什么)？ (我在任何文档中都找不到答案)
我猜想对于大小为n的列表,尾函数将是O(n),即只是将尾部复制到新列表并返回该列表.但话说回来,我不太了解Haskell的底层架构(我是语言的新手).
当然,我可以计时.但我还不知道如何在Haskell中计算时间,我也想了解Haskell如何处理问题,证明为什么它是O(n)/ O(1)或其他什么.
提前致谢 ：)
Haskell语言没有指定.但在GHC(最常用的实现)中,它是O(1).尾部不需要复制 – 在原始列表和只使用列表尾部的人之间共享是安全的 – 因为Haskell中的所有内容都是不可变的.
挑战问题：为什么除了列表的最后一个元素之外的所有init都在O(n)中运行？为什么上面的共享参数不适用于那里？
