algorithm - O(n) 中的 Frechet 距离

Question

我在许多文章中看到Fréchet 算法的复杂度是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]|)

并相应地更改iand j。
所以我可以得到 O(n) 的答案。

我错了吗？

标签： algorithmmathtime-complexitydistance

Answer 1

考虑下一个例子：

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