今天是《python算法教程》的第10篇讀書筆記秽五。筆記的主要內(nèi)容是使用python實現(xiàn)求最小點對的時間復(fù)雜度為O(nlogn)的算法。
平面最小點對問題介紹
在幾何學(xué)中檩小，有一個基本問題：在一個平面的n個點中浅妆，求距離最近的兩個點穿仪。
最直接的思路是遍歷所有的點對，通過比較所有點對的距離找出距離最近的兩點框舔，即暴力算法蹦玫。但是，這個思路的時間復(fù)雜度為O(n^2)刘绣。顯然樱溉，這種算法的時間復(fù)雜度是不能接受的。
因此纬凤，是否可以考慮通過分治法的思路福贞，將上述問題的解法的時間復(fù)雜度控制在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
#暴力算法主體函數(shù)
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
#生成器：生成橫跨跨兩個點集的候選點
def candidateDot(u,right,dis,med_x):
cnt=0
#遍歷right（已按橫坐標升序排序）。若橫坐標小于med_x-dis則進入下一次循環(huán)蜻底；若橫坐標大于med_x+dis則跳出循環(huán)骄崩；若點的縱坐標好是否落在在[u[1]-dis,u[1]+dis]，則返回這個點
for v in right:
if v[0]<med_x-dis:
continue
if v[0]>med_x+dis:
break
if v[1]>=u[1]-dis and v[1]<=u[1]+dis:
yield v
#求出橫跨兩個部分的點的最小距離
def combine(left,right,resMin,med_x):
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,med_x):
dis=calDis([u,v])
if dis<minDis:
minDis=dis
pair=[u,v]
return [pair,minDis]
#分治求解
def divide(seq):
#求序列元素數(shù)量
n=len(seq)
#按點的縱坐標升序排序
seq=sorted(seq)
#遞歸開始進行
if n<=1:
return None,float('inf')
elif n==2:
return [seq,calDis(seq)]
else:
half=int(len(seq)/2)
med_x=(seq[half][0]+seq[-half-1][0])/2
left=seq[:half]
resLeft=divide(left)
right=seq[half:]
resRight=divide(right)
#獲取兩集合中距離最短的點對
if resLeft[1]<resRight[1]:
resMin=combine(left,right,resLeft,med_x)
else:
resMin=combine(left,right,resRight,med_x)
pair=resMin[0]
minDis=resMin[1]
return [pair,minDis]
seq=[(random.randint(0,1000000),random.randint(0,1000000)) for x in range(500000)]
print("優(yōu)化算法",divide(seq))
