计算由fx =(x,x)完成的工作

Question

假设我有这个函数:( Haskell语法)

f x = (x,x)

该功能执行的工作(计算量)是多少？

起初我认为它显然是不变的,但是如果类型x不是有限的,那意味着x可以占用任意数量的内存？人们必须考虑到复制所做的工作x,对吗？

这让我相信函数完成的工作实际上是输入大小的线性.

这不是本身的功课,但是当我不得不定义函数完成的工作时:

f x = [x]

我相信哪个有类似的问题.

Answer 1

非正式地,完成的工作取决于您的语言的操作语义.Haskell,嗯,它很懒,所以你只需支付常数因素:

• 将指针推到x堆栈上
• 为...分配堆单元格 (,)
• 适用(,)于其论点
• 返回指向堆单元格的指针

完成.O(1)工作,当调用者查看结果时执行f.

现在,如果您查看内部,您将触发进一步的评估(,)- 并且该工作取决于评估x自身的工作.因为在Haskell x中共享引用,所以只评估一次.

因此,如果您完全评估结果,Haskell中的工作是O(x的工作).您的功能f仅添加常数因子.