球拍附加列表的复杂性

Question

>(define (f l) l) ;;;consider l to be a list 

这个功能应该是什么复杂性。据我说，它应该是O（长度为l），因为应该在堆上创建一个新列表并创建并返回一个新列表。

所以，如果它是O（长度l）则的复杂性（追加L1 L2）函数必须是O（长度L1 +长度L2），因为

(define (append l1 l2) 
    (if (null? l1) l2 [cons (car l1) (append (cdr l1) l2)])) 

在创建一个新的列表中的基本情况堆所以它需要花费时间O（L2）和递归需要时间O（L1），所以总的复杂性O（L1 + L2）

但在那段类追加是O（L1）类被教导，所以这是正确的？

Screenshot to prove that an entire new list is created on heap1（否则就改变L1或L2 L3必须改变！

Answer 1

(define (f l) l)简单地返回它的参数，不会复制它，所以其复杂度为O（1），而append定义你给副本只第一个列表，所以它的复杂度为O（长度L1）

想想看，你已经给了例子：(set! l2 '(4 5))不修改任何列表，它会修改全局变量l2，使它指向一个新的列表。所以l3不变。您可以使用set-cdr!或set-car!修改列表，如果您尝试此操作（假设您使用可修改列表的方言），您将看到l3也被修改。

Answer 2

伦佐假设论证已经在列表中，一些解释者可能是正确的。 eval的大部分驱动都是这样的，然后实际的lambda实现在apply之前执行evlis。

效率最高的Scheme实现将代码作为堆栈机器执行，因此每个变量只是一个偏移指向堆栈的指针，就像在本机程序中一样。对于(lambda l l)工作l需要从所有参数conse，以便在该函数的开始执行O((length n))任务，并且它有一个堆栈参数与该新创建列表的地址。然后它返回该地址，也许将它留在堆栈上。

append获取列表作为两个参数。因此它不需要从堆栈创建它们，因为堆栈有两个地址。 append制作l1的副本，当l1是空列表时，它使用l2而不用任何任何东西作为最后一对的cdr`。举个例子：

(define test1 '(1 2 3)) 
(define test2 '(4 5 6)) 
(define test3 (append test1 test2)) 
test3 ; ==> (1 2 3 4 5 6) 

(eq? (cdddr test3) test2) ; ==> #t (they are the same) 

(define test4 (append test1 '())) 
test4 ; ==> (1 2 3) 

(equal? test1 test4) ; ==> #t 
(eq? test1 test4) ; ==> #f (they just look the same) 

这里是参与第一append步骤：

(append '(1 2 3) '(4 5 6))      ; == 
(cons '1 (append '(2 3) '(4 5 6))     ; == 
(cons '1 (cons '2 (append '(3) '(4 5 6)))   ; == 
(cons '1 (cons '2 (cons 3 (append '() '(4 5 6)))) ; == 
(cons '1 (cons '2 (cons 3 '(4 5 6)))    ; == 

正如你可以看到它是O((+ 1 (length l1)))