40-算法解析及优化拓展

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

（1）时间复杂度：由程序可以看出，在函数HuffmanTree()中，if (HuffNode[j].weight<m1&& HuffNode[j].parent==−1)为基本语句，外层i与j组成双层循环：

i=0时，该语句执行n次；

i=1时，该语句执行n+1次；

i=2时，该语句执行n+2次；

……

i=n−2时，该语句执行n+n−2次；

则基本语句共执行n+（n+1）+（n+2）+…+（n+（n−2））=（n−1）*（3n−2）/2次（等差数列）；在函数HuffmanCode()中，编码和输出编码时间复杂度都接近n²；则该算法时间复杂度为O(n²)。

（2）空间复杂度：所需存储空间为结点结构体数组与编码结构体数组，哈夫曼树数组 HuffNode[]中的结点为n个，每个结点包含bit[MAXBIT]和start两个域，则该算法空间复杂度为O( n* MAXBIT)。

该算法可以从两个方面优化：

（1）函数HuffmanTree()中找两个权值最小结点时使用优先队列，时间复杂度为logn，执行n−1次，总时间复杂度为O( n logn)。

（2）函数HuffmanCode()中，哈夫曼编码数组HuffNode[]中可以定义一个动态分配空间的线性表来存储编码，每个线性表的长度为实际的编码长度，这样可以大大节省空间。