Prufer编解码的最优算法
讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(n log n)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.
标号树、Prufer编码、整数排序、最优算法
29
TP30(计算技术、计算机技术)
国家自然科学基金60172017;福建省自然科学基金A0510008
2008-05-26(万方平台首次上网日期,不代表论文的发表时间)
共4页
687-690