在球拍中附加列表的复杂性

Question

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

这个函数的复杂度应该是多少。根据我的说法，它应该是 O(length l)，因为应该在堆上创建一个新列表，然后创建并返回一个新列表。

所以如果它是 O(length l) 那么 (append l1 l2) 函数的复杂度必须是 O(length l1 + length l2) 因为

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

在基本情况下，在堆上创建一个新列表，因此需要时间 O(l2)，递归需要时间 O(l1)，因此总复杂度 O(l1 + l2)

但是我在 class 中被教导说在 class 中附加是 O(l1)，所以哪个是正确的？

Screenshot to prove that an entire new list is created on heap1（否则在更改 l1 或 l2 时 l3 必须已更改！！

Answer 1

(define (f l) l)只是returns它的参数，不复制它，所以它的复杂度是O(1)，而append 的定义，你给的副本 only 第一个列表，所以它的复杂度是 O(length l1).

考虑您给出的示例：(set! l2 '(4 5)) 不修改任何列表，它修改全局变量 l2，使其指向一个新列表。所以 l3 不变。您可以使用 set-cdr! 或 set-car! 修改列表，如果您尝试这样做（假设使用可以修改列表的方言），您将看到 l3 也被修改了。

Answer 2

Renzo 假设参数已经在列表中，并且一些解释器可能是正确的。 eval 的大多数实现都是这样做的，然后实际的 lambda 实现在 apply 之前执行 evlis。

最高效的 Scheme 实现将代码作为堆栈机器执行，因此每个变量都只是指向堆栈的偏移指针，就像在本机程序中一样。要使 (lambda l l) 工作，l 需要从所有参数中得出结论，这样在函数的开头它执行了一项 O((length n)) 任务，并且它有一个堆栈参数，地址为新创建的列表。然后它returns那个地址，也许是把它留在堆栈上。

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)))

在球拍中附加列表的复杂性

Complexity of appending lists in racket

complexity-theory

scheme

list

racket