一种构建最优二叉查找树的贪心算法

• 作者: 梁道雷 王秋芬
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 最优二叉查找树 哈夫曼树 贪心策略 复杂性
• 年，卷（期）: 2013,（7）
• 所属期刊栏目: 基金项目论文
• 页码范围: 57-61
• 页数: 5页
• 分类号: TP3
• 字数: 4922字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2013.07.017

摘要

分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现.该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破.实验结果表明:所提出的贪心算法的效率明显优于动态规划算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王秋芬	南阳理工学院计算机与信息工程学院	23	86	4.0	8.0
2	梁道雷	华东师范大学计算机系	23	121	6.0	10.0