今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点对的时间复杂度为O(nlogn)的算法。
在几何学中,有一个基本问题:在一个平面的n个点中,求距离最近的两个点。 最直接的思路是遍历所有的点对,通过比较所有点对的距离找出距离最近的两点,即暴力算法。但是,这个思路的时间复杂度为O(n^2)。显然,这种算法的时间复杂度是不能接受的。 因此,是否可以考虑通过分治法的思路,将上述问题的解法的时间复杂度控制在O(nlog2n)?答案是可以的。具体的算法讲解可参考下述博文:
但运用分治法求解上述问题时,需要注意一点,距离最小的两个点可能不在于同一个分组的点集中,而是分别来自于不同的点集中。
#计算两点的距离 import math def calDis(seq): dis=math.sqrt((seq[0][0]-seq[1][0])**2+(seq[0][1]-seq[1][1])**2) return dis #暴力算法主体函数 def calDirect(seq): minDis=float('inf') pair=[] for i in range(len(seq)): for j in range(i+1,len(seq)): dis=calDis([seq[i],seq[j]]) if dis <minDis: minDis=dis pair=[seq[i],seq[j]] return [pair,minDis]
#求出平面中距离最近的点对(若存在多对,仅需求出一对) import random import math #计算两点的距离 def calDis(seq): dis=math.sqrt((seq[0][0]-seq[1][0])**2+(seq[0][1]-seq[1][1])**2) return dis #生成器:生成横跨跨两个点集的候选点,由于点集是按纵坐标升序排序,right点集的点的纵坐标必定大于u的纵坐标,故只需检查纵坐标是否大于u[1]+dis,且只需最多检查right点集中纵坐标最小的6个点 def candidateDot(u,right,dis): cnt=0 for v in right: cnt+=1 if v[1]>u[1]+dis or cnt>3: break yield v #求出横跨两个部分的点的最小距离 def combine(left,right,resMin): med_x=(left[-1][0]-right[0][0])/2 dis=resMin[1] minDis=resMin[1] pair=resMin[0] for u in left: if u[0]<med_x-dis: continue for v in candidateDot(u,right,dis): dis=calDis([u,v]) if dis<minDis: minDis=dis pair=[u,v] return [pair,minDis] #分治求解 def divide(seq): #求序列元素数量 n=len(seq) #按点的纵坐标升序排序 seq=sorted(seq,key=lambda y:y[1]) #递归开始进行 if n<=1: return None,float('inf') elif n==2: return [seq,calDis(seq)] else: half=int(n/2) left=seq[:half] resLeft=divide(left) right=seq[half:] resRight=divide(right) #获取两集合中距离最短的点对 if resLeft[1]<resRight[1]: resMin=combine(left,right,resLeft) else: resMin=combine(left,right,resRight) pair=resMin[0] minDis=resMin[1] return [pair,minDis] seq=[(random.randint(0,100000),random.randint(0,1000000)) for x in range(100000)] print(sorted(seq,key=lambda y:y[0])) print("优化算法",divide(seq))
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句