algorithm - O(n) 中的 Frechet 距离

Question

我在许多文章中看到 Fréchet algorithm复杂度为 O(n^2)。
路径表示为 Q 和 P 数组，每个数组的大小为 n

如果我从 Q[0]、P[0] 开始检查所有可能性并选择最小值会怎样:

STP_i,j = min(|Q[i] - P[j+1]|, |Q[i+1] - P[j+1]|,|Q[i+1] - P[j]|)

并相应地更改i和j。
所以我可以在 O(n) 上得到答案。

我错了吗？

Answer 1

考虑下一个例子:

以黑色标记的点作为线条的开始。在第一步中，您的算法将在两条线上前进一个点。然而，在这种情况下，Fréchet 距离将是第一个红点和第三个蓝点之间的距离，但由于您的算法已经远离第一个点，它会给您一个更大的值。