理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題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とかはとりあえずな感じの定数。

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

木の高さが0のときは

  1. 左部分木を取る(c_1
  2. 右部分木を取る(c_1
  3. 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)になった。


n個のシンボルが存在するとして、一番出現頻度が大きいシンボルはh=1。一番出現頻度が小さいシンボルはh=n-1。だけどこれをもって出現頻度が大きいシンボルはO(1)で小さいシンボルはO(n^2)とは言えない気はするな。