请问scipy库中directed_hausdorff函数的时间复杂度是多少？

scipy.spatial.distance.directed_hausdorff 函数的时间复杂度由输入的两个点集（或图像转换后的点集）规模决定：

• 若第一个点集包含 M 个点，第二个点集包含 N 个点，函数的时间复杂度为 O(M*N)
• 原因是：有向豪斯多夫距离的计算逻辑是，先找出第一个集合中每个点到第二个集合所有点的最小距离，再从这些最小距离里取最大值，这个过程需要遍历两个集合的所有点对。

图像输入的特殊情况 #

如果输入是图像（比如你代码里的 img1 和 img2），函数会先将图像转换为非零像素的坐标点集，此时M和N对应两张图像中非零像素的数量，时间复杂度依然遵循 O(M*N)。

示例代码回顾 #

from scipy.spatial.distance import directed_hausdorff

score = directed_hausdorff(img1, img2)[0]
print(score)

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