乐正

Actions speak louder than words.

Sicp-ex2-72

问题

考虑你在练习2.68中设计的编码过程。对于一个符号的编码,计算步数的增长速率是什么? 请注意,这个时候需要把在每个节点中检查符号表所需要的步数包括在内。一般性地回答这 个问题是非常困难的。现在考虑一类特殊情况,其中的n个符号的相对频度如练习2.71所描 述的。请给出编码最频繁的符号所需的步数和最不频繁的符号所需的步数的增长速度(作为 n的函数)。

解答

这种情况下,编码出现最频繁的符号所需的步数是$\Theta (1)$,其中加密的步数和检查符 号都是$\Theta (1)$。

编码出现最不频繁的符号其检查符号所需步数为$n \times (n-1) \times \cdots \times 1$。 所以所需要的步数是$\Theta (n^2)$。

draft

« sicp-ex2-71 sicp-ex2-73 »

Comments