货郎担问题的几何解法

被引：10

作者：

周培德

机构：

[1] 北京理工大学计算机系

来源：

软件学报 | 1995年 / 07期

关键词：

几何算法，算法复杂性，货郎担问题;

D O I：

10.13328/j.cnki.jos.1995.07.006

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数．

引用

收藏

页数：5

相关论文

共 2 条

[1] 求凸壳顶点的一种算法 [J].

周培德 .

北京理工大学学报, 1993, (01) :69-72

[2]

算法设计与分析[M]. - 机械工业出版社 , 周培德编著, 1992