ラケットでの追加リストの複雑さ

Question

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

この機能の複雑さはどのようなものですか。私によれば、ヒープ上に新しいリストを作成し、新しいリストを作成して返すので、O（長さl）にする必要があります。

それはO（長さL）である場合、新しいリストが作成された基本ケースであるため

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

それでは複雑さ（L1、L2を追加）の機能は、O（長さ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)を変更していなければなりません単にはそれををコピーしません、その引数を返し、そうその複雑さはappend定義しばらくO（1）であり、あなたがコピーのみ最初のリストを与えている、とそうその複雑さはO（長さL1）であることを

をあなたが与えていることを例に考えてみます。(set! l2 '(4 5))は、任意のリストを変更しない、それがグローバル変数l2、作りを修正しますそれ新しいリストを指しています。したがってl3は変更されません。 set-cdr!またはset-car!を使用してリストを変更できます。リストを変更できる方言を使用すると仮定すると、l3も変更されています。

Answer 2

レンゾはすでに引数がリストにあり、いくつかのインタプリタが正しいと仮定しています。 evalのほとんどの実装はこのようになり、実際のラムダ実装はの前にevlisとなります。

最も効率的なScheme実装は、コードをスタックマシンとして実行するため、すべての変数はネイティブプログラムと同様にスタックへのオフセットポインタに過ぎません。 (lambda l l)が動作するためには、lは、関数の最初にO((length n))というタスクを実行し、その新たに作成されたリストのアドレスを持つ1つのスタック引数を持つように、すべての引数から引き継ぐ必要があります。次に、そのアドレスをスタックに戻して返します。

appendは、2つの引数としてリストを取得します。したがって、スタックには2つのアドレスがあるため、スタックからそれらを作成する必要はありません。 appendはl1のコピーを作成し、l1が空のリストの場合は、最後のペアのcdrとして何もせずにl2を使用します。例として：ここで

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