Excersice 2.63
- a. どちらのプログラムも、(左の枝 要素 右の枝)というリストを再帰的に作るので、同じ結果になる。
- b. tree->list-1の方が遅い。リストの結合にappendを使っているから.
- (append x y) は、O(xの要素数)の時間が掛かる。
tree->list-1で要素数nのバランス木をリストにするのにf(n)掛かるとする.
- appendにn/2ステップ、
- (tree->list-1 (left-branch)), (tree->list-1 (right-branch))にそれぞれf(n/2)ステップ
掛かるので、ざっくりと次の関係が成り立つ。
f(n) = n/2 + 2f(n/2)
これから、f(n) = O(n log(n))となる。tree->list-2の方は、O(n)しか掛からない。
# 合ってるかな。。。
