【SICP練習】90練習2.63

練習2.63

この2つのセグメントコードの違いは,2番目のセグメントが反復を用い,計算時間を大幅に低減できると信じていることである.では、まず最初の問題をテストします.必要なコードはみんな先にノックします.次に、図2〜16の3本の木を定義します.

(define tree-1 (make-tree 7 (make-tree 3 (make-tree 1 '() '()) (make-tree 5 '() '())) (make-tree 9 (make-tree '()) (make-tree 11 '() '()))))
(define tree-2 (make-tree 3 (make-tree 1 '() '()) (make-tree 7 (make-tree 5 '() '()) (make-tree 9 '() (make-tree 11 '() '())))))
(define tree-3 (make-tree 5 (make-tree 3 (make-tree 1 '() '()) '()) (make-tree 9 (make-tree 7 '() '()) (make-tree 11 '() '()))))

これらは誰もが定義すると信じられており、make-treeの3つのパラメータは結点、左右の枝の順である.この3本の木に対して、2段のコードは6回のテストをして、得た結果は間違いなく一致します:(1 3 5 7 9 11)
では,a小問題が完成しても,b小問題はこの2つの関数の実行効率にかかわるため,それらを分解して展開せざるを得ない.
最初の木を用いて,展開過程をそれぞれ2つの関数で実証した.展開の過程は本当に長いが,収穫もあり,最後までにappendが6回,consも6回,tree−1のノードが6個(もちろん,tree−2とtree−3も6個のノード)であることが分かった.従ってappendとconsを用いた回数とノードの個数は正に相関していると結論した.一方appendの複雑度はconsより高く,前者はn後者は1であるため,この関数の複雑度はn方である.
tree->list-2の展開過程は類似しており,その複雑さはnである.したがって,両者の最終結果は同じであるが,2番目の関数はより迅速である.
訪問ありがとうございます.ご協力をお願いします.注目やコレクション、コメント、いいねを歓迎します.
斧正と質問を得るために、転載は出典を明記してください.http://blog.csdn.net/nomasp