球拍附加列表的复杂性
>(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必须改变!
(define (f l) l)
简单地返回它的参数,不会复制它,所以其复杂度为O(1),而append
定义你给副本只第一个列表,所以它的复杂度为O(长度L1)
想想看,你已经给了例子:(set! l2 '(4 5))
不修改任何列表,它会修改全局变量l2
,使它指向一个新的列表。所以l3
不变。您可以使用set-cdr!
或set-car!
修改列表,如果您尝试此操作(假设您使用可修改列表的方言),您将看到l3
也被修改。
伦佐假设论证已经在列表中,一些解释者可能是正确的。 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)))
喔,所以我的一套解释!是不正确的,感谢 – Naman
但effiecent方案实现比如球拍的Ikarus保持它们的参数在堆栈上。堆栈分配的参数如何变成O(1)对的链? – Sylwester