SICP
SICP勉強会してるので、 気が向いたら知見書いていけたらなぁと
exe2.63
(define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '()))
問題はtree->list1とtree->list2が同じリストを生成するのか、 オーダーはどうかである。 生成されるリストは順序ありリストという縛りがある。
前者は、生成されるリストは 一意に決定されるので、一つに定まる。
後者は、 tree->list1は
こんな感じの順番で評価される
tree->list2は
はこんな感じ.
これだけの違いしかなく、 それぞれ要素数nの場合 tree->list1はn回、 tree->list2(copy-to-list)もn回呼ばれる。
ここでtree->list1はappendを用いてlistの結合をしているので、 さらにO(n)かかる。 tree->list2はconsで済んでいる。
結果的にtree->list1は O(n2)、 tree->list2は O(n)
ハフマン木が面白かったから、 そこまで書こうと思ったけど疲れたから終わり