跳转至

距离

OI 中常用的几类距离

曼哈顿距离

对于平面上两点 A(x_1, y_1), B(x_2, y_2)Dis(A, B) = |x_1-x_2| + |y_1-y_2|

一般来讲，我们只会用到二维平面上的曼哈顿距离

切比雪夫距离

对于平面上两点 A(x_1, y_1), B(x_2, y_2)Dis(A, B) = \max(|x_1-x_2| , |y_1-y_2|)

对于两个 n维向量 \vec A(x_{11}, x_{12}, \cdots,x_{1n})\vec B(x_{21}, x_{22}, \cdots,x_{2n})

Dis(A, B) = \max\limits_i(|x_{1i}-x_{2i}|)

欧几里得距离（又称欧氏距离）

欧几里得距离是两点的直线距离。

对于平面上两点 A(x_1, y_1), B(x_2, y_2)Dis(A, B) = \sqrt{(x_1-x2)^2+(y1-y2)^2}

对于两个 n维向量 \vec A(x_{11}, x_{12}, \cdots,x_{1n})\vec B(x_{21}, x_{22}, \cdots,x_{2n})

Dis(A, B) = \sqrt{\sum\limits_{k=1}^n(x_{1k}-x_{2k})^2}

L_m距离

一般地，我们定义平面上两点 A(x_1, y_1), B(x_2, y_2)之间的 L_m距离为

dist~L_m = (|x_1-x_2|^m+|y1-y2|^m)^{\frac{1}{m}}

特殊的， L_2距离就是欧几里得距离， L_1距离就是曼哈顿距离。

汉明距离

汉明距离是两个字符串之间的距离，它表示两个长度相同的字符串对应位字符不同的数量

我们可以简单的认为对两个串进行异或运算，结果为 1 的数量就是两个串的汉明距离。

当然，还有其他的一些距离，但是在 OI 中并不常用，有兴趣的话可以了解一下。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论