在做求平面内最近点对的问题时,使用两种不同的比较方法求最小距离,算法效率在100000输入规模下相差2~3倍,很费解,想向大家求助。
具体来说只有求两点距离的方法是不一样的(然而却导致了不同):
一是先一直用平方表示距离,最后输出算开根
if (s == e) return MAX; //如果只有一个点返回无限大if (s + 1 == e) return square(ar[s], ar[e]);//如果只有两个点返回开根后的距离
二是每次都直接算出开根以后的距离
if (s == e) return MAX; //如果只有一个点返回无限大if (s + 1 == e) return dis(ar[s], ar[e]);//如果只有两个点返回开根后的距离
以上两种情况都是递归到底后执行,此外还有比较中间是否有最小距离时需要用到
curmin = min(curmin, square(ar[sr[i]], ar[sr[j]])); curmin = min(curmin, dis(ar[sr[i]], ar[sr[j]]));//(当前求得的两边最小值,优艾设计网_PS交流中间最小值)
double dis(Node a, Node b) { return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); }//返回点与点之间的距离 double square(Node a, Node b) { returnpow(a.x - b.x, 2) + pow(a.y - b.y, 2); } //square()和dis()除了是否开根以外没有任何差别。
两种方法在100000规模下运行20次取平均运行时间如图1和图2所示
图1 dis方法
图2 square方法
输入使用随机数,在随机数中规模大约平均在10的4次方,显然square产生的数字要比dis大得多,每次比较的数字也大的多,比较的复杂度是O(n)的。但是用同样的类型存储数据,也都没有溢出,占位应该是相同的,而且比较是大家都要比较的,dis方法只是数比较小,何况dis每次运算是通过计算平方再开根,多了开根这一步,为什么用dis方法反而会快呢?如何理解数据规模对比较的影响呢?
没有脑子的迷糊 1小时前 优艾设计网_PS论坛
个人觉得很有可能是你其他部分造成了你这个结果。
rmzRUZXE 1小时前 优艾设计网_电脑技术
我在很多情况下都是不开方开判断大小或者是其他,只有需要结果的时候才开方。
tree娟 1小时前
不知道你的其他优艾设计网_Photoshop论坛部分。
背口袋 优艾设计网_设计 1小时前
这样判断大小的时候少一次开方,可以节省很多。
精彩评论