摘要
王志强等于 1998年提出了一个计算平面点集凸包的新算法 ,并且声称该算法的最坏时间复杂度为 O(n) ,从而为线性时间排序提供了可能性 .该文对王志强等提出的求平面点集凸包算法的时间分析提出不同观点 ,进一步明确了平面点集凸包算法和排序算法的时间下界为 Ω(nlogn)
Wang Zi Qiang et al presented a new algorithm for computing the convex hull of a planar point set in 1998, and claimed that the worst case time complexity of the algorithm is O(n ), which can lead to a linear time algorithm for sorting. This correspondence gives a different standpoint on the cost time analysis of the algorithm, and further make clear that the lower bound to these problems under algebraic decision tree model is still Ω(n log n ).
出处
《计算机学报》
EI
CSCD
北大核心
2002年第6期670-672,共3页
Chinese Journal of Computers
