C++ 中的闵氏距离查找

在计算几何和机器学习的广阔领域中，量化对象之间差异的能力至关重要。这种需求催生了许多距离度量的发展，每种度量都针对不同的应用和场景。在这些度量中，闵可夫斯基距离作为一种多功能且强大的工具脱颖而出，用于度量 n 维空间中的差异。

以杰出的数学家赫尔曼·闵可夫斯基的名字命名，闵可夫斯基距离是他几何学和时空工作的自然延伸。闵可夫斯基的开创性贡献为现代距离度量奠定了基础，为理解空间和时间的基本结构提供了深刻见解。他将闵可夫斯基空间（一种将时间作为第四维扩展传统欧几里得空间的概念）的思想，彻底改变了我们对时空几何的理解，并为数学、物理学和计算机科学中使用的各种距离度量铺平了道路。

闵可夫斯基距离的本质在于其概括其他著名距离度量（如欧几里得距离、曼哈顿距离和切比雪夫距离）的能力。通过引入一个决定距离度量阶数的参数 r，闵可夫斯基距离涵盖了一系列距离度量，每种度量都具有独特的性质和应用。当 r=1 时，闵可夫斯基距离简化为曼哈顿距离，计算每个维度上绝对差的总和。当 r 趋近于无穷大时，闵可夫斯基距离收敛于切比雪夫距离，侧重于任何维度上的最大绝对差。当 r=2 时，闵可夫斯基距离对应于我们熟悉的欧几里得距离，它在空间中捕获两个点之间的直线距离。在 C++ 等计算框架中实现闵可夫斯基距离，使从业者能够在各种领域利用其多功能性和效率。通过将闵可夫斯基距离的数学公式封装在软件函数中，开发人员可以无缝地将此距离度量集成到他们的算法中，用于聚类、分类、图像处理等任务。实现的简单性掩盖了底层数学的复杂性，使得闵可夫斯基距离适用于广泛的应用和行业。

在本文中，我们将踏上探索闵可夫斯基距离的复杂性及其在计算几何和机器学习中的应用的旅程。我们将深入探讨闵可夫斯基贡献的历史背景，揭示闵可夫斯基距离的数学公式，并演示如何在 C++ 中有效地实现它。此外，我们将讨论闵可夫斯基距离在不同领域的实际应用，展示其在当代计算任务中的相关性和重要性。加入我们，一起揭开闵可夫斯基距离的奥秘，这是一个永恒的概念，将继续塑造计算科学和工程的格局。

闵可夫斯基距离的历史

闵可夫斯基距离的历史与赫尔曼·闵可夫斯基的开创性工作息息相关，他是一位富有远见的数学家，其贡献为现代几何学和理论物理学奠定了基础。闵可夫斯基于 1864 年出生在立陶宛，当时是俄罗斯帝国的一部分，他在德国接受教育，并在费利克斯·克莱因和阿道夫·赫尔维茨等著名数学家的指导下，他的智力和数学才华很快就显现出来。

闵可夫斯基的学术生涯曾任教于多个享有盛誉的机构，包括柯尼斯堡大学和哥廷根大学，在那里他与数学和物理学领域的顶尖人物合作。他的早期研究集中在数论和代数几何领域，他在二次型理论和数论几何方面做出了重要贡献。

然而，闵可夫斯基最持久的贡献在于他在几何学和理论物理学方面的工作，特别是他发展了闵可夫斯基空间的概念。在1907年，闵可夫斯基引入了时空的概念，作为一个统一的框架来理解宇宙的几何。借鉴阿尔伯特·爱因斯坦狭义相对论的见解，闵可夫斯基认识到空间和时间是内在联系的，形成了一个四维连续体，其中事件由其在时空中的坐标来描述。

闵可夫斯基时空几何公式的核心是引入一个度量张量，该张量量化了时空中两个事件之间的间隔。这个度量张量称为闵可夫斯基度量，它包含了时空的几何结构，并在爱因斯坦的广义相对论中起着至关重要的作用。闵可夫斯基的概念飞跃为更深入地理解空间、时间和引力的性质铺平了道路，为现代理论物理学奠定了基础。

在数学领域，闵可夫斯基关于几何学的研究超越了时空，包括对 n 维空间中距离度量的研究。他引入了闵可夫斯基距离的概念，作为欧几里得距离、曼哈顿距离和切比雪夫距离等距离度量的推广。闵可夫斯基距离定义为每个维度上绝对差的 r 次幂之和的 r 次方根，它为测量多维空间中点之间的差异提供了一个统一的框架。

闵可夫斯基距离的意义远远超出了其数学上的优雅；它在计算几何、机器学习和数据分析等各个领域都发挥着基石作用。通过在一个框架内包含一系列距离度量，闵可夫斯基距离在各种领域提供了无与伦比的多功能性和适用性。总之，闵可夫斯基距离的历史与赫尔曼·闵可夫斯基的富有远见的见解密不可分，他对几何学、物理学和数学的贡献继续塑造着我们对宇宙的理解，并激励着一代又一代的学者和科学家。

理解闵可夫斯基距离

在距离度量的广阔领域中，闵可夫斯基距离因其作为量化多维空间中对象之间差异的多功能且强大的工具而脱颖而出。该距离度量以杰出的数学家赫尔曼·闵可夫斯基的名字命名，它提供了一个统一的框架，概括了包括欧几里得距离、曼哈顿距离和切比雪夫距离在内的几种著名距离度量。要掌握闵可夫斯基距离的本质，必须深入研究其数学公式，并理解它如何封装多维空间的几何结构。

其核心在于，闵可夫斯基距离用于测量 n 维空间中两点 P 和 Q 之间的距离。与计算两点之间直线距离的熟悉欧几里得距离不同，闵可夫斯基距离考虑了每个维度上的距离，并使用幂函数将它们组合起来。n 维空间中两点 P 和 Q 之间的闵可夫斯基距离的数学表达式为

这里，p_i 和 q_i 分别表示点 P 和 Q 的第 i 个坐标。参数 r 决定了闵可夫斯基距离的阶数。当 r=1 时，闵可夫斯基距离简化为曼哈顿距离，也称为 L₁ 范数，它测量每个维度上绝对差的总和。这对应于在城市网格状街道上行驶的距离，其中只允许水平和垂直移动。

另一方面，当 r=2 时，闵可夫斯基距离变为欧几里得距离，表示为 L₂ 范数，它计算空间中两点之间的直线距离。此距离度量从几何学中很熟悉，其中它表示两点之间的最短路径，类似于连接它们的直线。

当 r 趋近于无穷大时，闵可夫斯基距离收敛于切比雪夫距离，该距离测量任何维度上的最大绝对差。换句话说，它仅关注两点相应坐标之间的最大差异。

通过改变 r 的值，我们可以对这些不同的距离度量进行插值，为量化多维空间中的差异提供一系列选项。这种灵活性在机器学习和数据分析中尤其有价值，在这些领域中，不同的距离度量可能更适合特定的任务或数据集。

在 C++ 等计算框架中实现闵可夫斯基距离，包括将数学公式封装在软件函数中。此函数接收两个点 P 和 Q 的坐标作为输入，以及指定闵可夫斯基距离阶数的参数 r。然后，它遍历每个维度，计算绝对差的 r 次幂，将它们加起来，最后取总和的 r 次方根以获得闵可夫斯基距离。

在 C++ 中实现闵可夫斯基距离

现在，让我们深入研究在 C++ 中实现闵可夫斯基距离。我们将创建一个简单的函数来计算 n 维空间中两点之间的闵可夫斯基距离。

输出

Minkowski distance between the points: 5.19615

说明

1. 函数定义 - minkowskiDistance

• 此函数计算由向量 p 和 q 表示的两点之间的闵可夫斯基距离。
• 它接受三个参数
• p: 一个表示第一个点坐标的向量。
• q: 一个表示第二个点坐标的向量。
• r: 一个表示闵可夫斯基距离阶数的整数。
• 它初始化一个变量 sum 来存储绝对差的 r 次幂的总和。
• 它使用循环遍历点 P 的每个维度，并计算 P 和 Q 相应坐标之间的绝对差。
• 它将每个绝对差提高到 r 的幂，并将其添加到总和中。
• 最后，它返回总和的 r 次方根，这表示点之间的闵可夫斯基距离。

2. 执行

• 在此特定示例中，point1 为 {1.0, 2.0, 3.0}，point2 为 {4.0, 5.0, 6.0}。
• 闵可夫斯基距离的阶数设置为 2，这对应于欧几里得距离。
• 使用欧几里得距离公式计算两点 {1.0, 2.0, 3.0} 和 {4.0, 5.0, 6.0} 之间的闵可夫斯基距离。
• 然后将计算出的距离打印到控制台。

复杂度分析

时间复杂度分析

1. 迭代点：minkowskiDistance 函数中的循环遍历点 p 和 q 的每个维度。此循环的时间复杂度为 O(n)，其中 n 是维度数（向量 p 和 q 的大小）。
2. 计算绝对差和幂：在循环内部，我们计算点 p 和 q 的相应坐标之间的绝对差，并将它们提高到 r 的幂。此操作对每个维度需要恒定的时间，并且由于我们对每个维度执行此操作，因此它为总体时间复杂度贡献了 O(n)。
3. 求和：计算绝对差的 r 次幂后，我们对它们求和。此求和涉及遍历所有维度并将结果相加。由于我们对每个维度执行此操作，因此它也为时间复杂度贡献了 O(n)。
4. 根运算：最后，我们取总和的 r 次方根。此操作涉及将总和提高到 1/r 的幂，这可以在恒定的时间内计算。因此，它不影响总体时间复杂度。

总的来说，minkowskiDistance 函数的时间复杂度为 O(n)，其中 n 是维度数。

空间复杂度分析

1. 输入向量：输入向量 p 和 q 各自需要与维度数成比例的空间，即 O(n)。
2. 局部变量：该函数使用 sum 和 i 等局部变量，这些变量需要恒定的空间，与输入大小无关。
3. 返回值：函数的返回值是一个标量（double），需要恒定的空间。

总的来说，实现的空間复杂度为 O(n)，其中 n 是维度数。

时间复杂度：minkowskiDistance 函数的时间复杂度为 O(n)，其中 n 是维度数。这种复杂度源于遍历输入点的每个维度并为每个维度执行恒定时间的操作。

空間复杂度：实现的空間复杂度也为 O(n)，其中 n 是维度数。这种复杂度源于存储输入向量 p 和 q 所需的空间，这些空间与维度数成正比。总的来说，该实现为计算 n 维空间中两点之间的闵可夫斯基距离提供了一种高效且可扩展的解决方案，其时间和空间复杂度都与维度数线性相关。

结论

总而言之，理解闵可夫斯基距离包括掌握其数学公式及其作为其他距离度量的推广的作用。通过对不同阶数的闵可夫斯基距离进行插值，从业者可以定制其距离度量以适应特定的应用和数据集。凭借其多功能性和在多维空间中的适用性，闵可夫斯基距离仍然是计算几何、机器学习和数据分析的基石，它为理解对象之间的差异提供了深刻见解，并促进了各种计算任务。