|
|||||
|
|
| 一种构建最优二叉查找树的贪心算法 | |
| 作者单位： | ;1.南阳理工学院计算机与信息工程学院;2.华东师范大学计算机系;3.浙江理工大学理学院 |
| 摘 要： | 分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。 |
| 关 键 词： | 最优二叉查找树 哈夫曼树 贪心策略 复杂性 |
A GREEDY ALGORITHM FOR CONSTRUCTING OPTIMAL BINARY SEARCH TREE |
|
| Abstract: | |
| Keywords: | |