依此思路，合并步骤耗时为 O(n
2
)。整个算法所需计算时间 T(n)应满足:
T(n)=2T(n/2)+O(n
2
)
它的解为 T(n)=O(n
2
)，即与合并步骤的耗时同阶，显示不出比用穷举的方法
好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启
发我们把注意力放在合并步骤上。
为了使问题易于理解和分析，我们先来考虑一维的情形。此时 S 中的 n 个点
退化为 x 轴上的 n 个实数 x
1
,x
2
,..,x
n
。最接近点对即为这 n 个实数中相差最小的 2
个实数。我们显然可以先将 x
1
,x
2
,..,x
n
排好序，然后，用一次线性扫描就可以找
出最接近点对。这种方法主要计算时间花在排序上，因此如在排序算法中所证
明的，耗时为 O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对
这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的
情形。
假设我们用 x 轴上某个点 m 将 S 划分为 2 个子集 S
1
和 S
2
，使得 S
1
={x S|∈
x≤m}；S
2
={x S|x>m}∈ 。这样一来，对于所有 p S∈
1
和 q S∈
2
有 p<q。
递归地在 S
1
和 S
2
上找出其最接近点对{p
1
,p
2
}和{q
1
,q
2
}，并设 δ=min{|p
1
-p
2
|,|
q
1
-q
2
|}，S 中的最接近点对或者是{p
1
,p
2
}，或者是{q
1
,q
2
}，或者是某个{p
3
,q
3
}，
其中 p
3
S∈
1
且 q
3
S∈
2
。如图 1 所示。
评论0