Exercise 2.72 · 习题

Exercise 2.72: Consider the encoding procedure

that you designed in Exercise 2.68. What is the order of growth in the

number of steps needed to encode a symbol? Be sure to include the number of

steps needed to search the symbol list at each node encountered. To answer

this question in general is difficult. Consider the special case where the

relative frequencies of the n symbols are as described in Exercise 2.71,

and give the order of growth (as a function of n) of the number of

steps needed to encode the most frequent and least frequent symbols in the

alphabet.

练习 2.72：考虑你在练习 2.68 中设计的编码过程。对一个符号编码所需步骤数的增长阶是多少？请务必计入在每个遍历节点处搜索符号表所需的步骤数。一般情况下回答这个问题是困难的。考虑练习 2.71 中所描述的 n 个符号相对频率的特殊情形，给出编码最高频符号和最低频符号所需步骤数关于 n 的增长阶。