問題2-72 (2.3.4 Example: Huffman Encoding Trees)

encode-symbolの計算量を計算すればいいっぽい。
encode-symbolはsymbol-in-tree?とelement-of-set?を呼び出しているので、このへんも考慮する。

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))
  
(define (symbol-in-tree? x tree)
  (let ((symbol-set (symbols tree)))
    (element-of-set? x symbol-set)))

(define (encode-symbol symbol tree)
  (let ((left (left-branch tree))
	(right (right-branch tree)))
    (cond ((leaf? tree) '())
          ((symbol-in-tree? symbol left)
	   (cons 0 (encode-symbol symbol left)))
	  ((symbol-in-tree? symbol right)
	   (cons 1 (encode-symbol symbol right)))
	  (else (error symbol "does not exist in the tree")))))

symbol-in-tree?の計算量は、element-of-set?の計算量とおなじです。element-of-set?のset中の要素数をnとすると、その計算量は
$S(n)=\frac{\sum_{i=1}^n c_ei+c_en}{n+1}=c_e\frac {n(n+3)}{2(n+1)}$
かな。 $c_e$ はテキトーな定数。要素が $i (1\leq i \leq n)$ 番目にある事象とset内に存在しない事象が等確率で起こると仮定。必ず存在すると仮定した方がきれいになった予感はする。

encode-symbolは木の高さ $h$ が1以上のとき、以下のような計算をしている。 $c_1,c_2$ とかはとりあえずな感じの定数。

左部分木を取る（ $c_1$ ）
右部分木を取る（ $c_1$ ）
leafかどうかの判断（ $c_2$ ）
symbol-in-tree?を呼ぶ。要素数は $h+1$ 。（ $c_e\frac {h+1}2$ ）
木の高さを $h-1$ としてencode-symbolを呼ぶ

木の高さが0のときは

左部分木を取る（ $c_1$ ）
右部分木を取る（ $c_1$ ）
leafかどうかの判断（ $c_2$ ）

なかんじです。

そういうわけで、encode-symbolの計算量を $T(h)$ とすると
$T(h)=\begin{cases}2c_1+c_2+c_e\frac {(h+1)(h+4)}{2(h+2)}+T(h-1)&(h\geq 1)\\2c_i+c_2&(h=0)\end{cases}$
なのかな。これ解いたら $T(h)=h\left(2c_1+c_2+c_e\frac {(h+1)(h+4)}{2(h+2)}\right)+2c_1+c_2=O(h^2)$ になった。