SICP 問題 2.72（特殊なケースの探査ステップ数を求める）

問題

問題 2.68 で設計した符号化手続きを考える。記号を符号化するのに必要なステップ数の増加の程度は何か。各節で記号のリストを探索するのに必要なステップ数を忘れないように。
この問題に一般的に答えるのは難しい。n 個の記号の相対頻度が問題 2.71 にあるような特別な場合を考え、アルファベットの最高頻度と最低頻度の記号を符号化するのに必要なステップ数の（n の関数としての）増加の程度を答えよ。

解答

前半の問題の意味がわから〜ん。「ステップ数の増加の程度は何か」と問うているくせに、後半の先頭で、「この問題に一般的に答えるのは難しい。」とか抜かしてるってのは一体どーゆー了見だよ。
つーわけで前半は無視。料理したくても材料がねぇもの。ひょっとして訳に問題あり？

ま、いいや。問題 2.71 の例を元に解けって言ってる後半部分を解いてみよう。一応シンボルをビット列に変換する手続きを再掲しておくか。

(define (encode-symbol symbol tree)

  (define (element-of-tree? symbol tree)
    (pair? (memq symbol (symbols tree))))

  (let loop ((branch tree))
    (if (leaf? branch)
	'()
	(let ((left (left-branch branch))
	       (right (right-branch branch)))
	   (cond ((element-of-tree? symbol left)
		  (cons 0 (loop left)))
		 ((element-of-tree? symbol right)
		  (cons 1 (loop right))))))))

最高頻度の記号を符号化するのに必要なステップ数

問題 2.71 の場合、最高頻度の値は一発目でヒットするはず。
一発目でヒットする前に、シンボルのリストをチェックするが、そのリスト中にはシンボルが n 個格納されている。
なので、ステップ数としては、n。
増加の割合なので、この n を微分して、解答は Θ(1)。

・・・あってんのか？

最低頻度の記号を符号化するのに必要なステップ数

最低頻度の記号は、最後まで探査しないとお目当てのシンボルにヒットしない。
ある時点の探査回数を k とした場合、これが増える度に encode-symbol と element-of-tree? 内で探査される回数を表にしてステップ数の合計値を概算してみる。

①：k	②：encode-symbol 内の loop が呼ばれる回数	③：element-of-tree? が呼ばれる回数	④：② × ③
1	1	n-1	n-1
2	1	n-2	n-2
・	・	・	・
・	・	・	・
・	・	・	・
k	1	n-k	n-k
・	・	・	・
・	・	・	・
・	・	・	・
n	1	1	1