Haskell的“尾部"函数具有什么时间复杂度? [英] What Time Complexity Does Haskell's "tail"-Function Have?

问题描述

当我对自己思考的时候，我正在阅读有关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的“尾部"函数具有什么时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！