度量空间中∆-伪中位数近似求解O(n²)算法设计问题

核心思路 #

利用伪中位数邻域的超半数特性和度量空间的三角不等式推导可行判定条件，无需知道伪中位数x*的具体位置即可通过点集内两两距离计算筛选符合要求的点。

具体算法步骤 #

• 对每个点x_i ∈ Y（i=1,2,…,n）：
  1. 初始化计数变量cnt = 0
  2. 遍历所有点x_j ∈ Y，若d(x_i, x_j) ≤ 2∆，则cnt += 1
  3. 若cnt > n/2，直接返回x_i作为结果

正确性证明 #

我们先给出已知条件：存在集合S⊆Y，|S|>n/2，所有z∈S满足d(z, x*) ≤ ∆。

1. 对任意z∈S，S中所有点到z的距离都满足d(z, z') ≤ d(z, x*) + d(x*, z') ≤ 2∆，因此z对应的计数必然≥|S|>n/2，说明算法一定能找到符合计数条件的点。
2. 设算法返回的点为x_i，对应满足d(x_i, x_j) ≤ 2∆的点集为T，|T|>n/2。由于|T|+|S|>n，两个集合必有公共元素z∈T∩S。由三角不等式可得：
   d(x_i, x*) ≤ d(x_i, z) + d(z, x*) ≤ 2∆ + ∆ = 3∆ ≤ 4∆
   完全满足题目要求的距离条件。

时间复杂度分析 #

外层遍历n个点，每个点需要遍历所有n个点计算距离，单次距离计算时间为O(1)，总时间复杂度为O(n²)，符合要求。 #

内容的提问来源于stack exchange，提问作者blades