球拍附加列表的複雜性

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