摘要
分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。
We analyses in the paper the similarity and difference between the optimal binary search tree and the Huffman tree, and propose a greedy algorithm for resolving the optimal binary search tree, as well as proving the correctness of the algorithm. At the same time, we use C ＋ ＋ programming language to encode and implement it. The time complexity of the algorithm is 0 （n2） and the space complexity is 0 （n）, the breakthrough of the ＂order＂ of space complexity is achieved. Experimental results show that the greedy algorithm proposed is obviously better than the dynamic programming algorithm in efficiency.
出处
《计算机应用与软件》
CSCD
北大核心
2013年第7期57-61,共5页
Computer Applications and Software
基金
国家自然科学基金项目(90818013)
华东师范大学211重点项目(521B0108)
浙江理工大学基金项目(yb07002)
关键词
最优二叉查找树
哈夫曼树
贪心策略
复杂性
Optimal binary search tree Huffman tree Greedy strategy Complexity
