4

Douglas-Peucker 线简化算法的最坏情况时间复杂度为 O(n²)。然而，要让一条线真正触发这种最坏的情况，有两件事必须同时出现“错误”：

  • 阈值必须设置得如此之低，以保持大多数顶点
  • 在每个递归步骤中，与当前端点之间的线偏差最大的顶点必须靠近（就其在线索引而言，而不是其欧几里德位置而言）到端点之一。（如果相反，与直线偏差最大的顶点的索引足够接近当前端点之间的中间，则该算法应导致深度的递归二进制细分log(n)，从而导致整体时间复杂度为O(n log(n))。）

虽然第一个标准很容易触发（只需将公差阈值设置为 0.0），但我还没有找到满足第二个标准的线。

那么是否有一条导致最坏情况行为的简单示例行（最好是触发明显最坏情况的行，其中每个递归步骤中偏差最大的点直接连接到行的端点之一；但是任何其他示例也很好）？

4

1 回答 1

5

所以 Vincent van der Weele 似乎是对的，一条振幅增加的简单锯齿线将触发 Douglas-Peucker 算法的 O(n²) 最坏情况：

在此处输入图像描述

在这种情况下，与连接两个端点的直线距离最长的顶点将始终是与右侧端点直接相邻的顶点。因此，Douglas-Peucker 算法在这里需要 O(n) 个细分步骤，其中每个步骤只刮掉最右边的顶点，因此需要遍历剩余的 O(n) 个顶点以找到距离最长的顶点 - 给出一个O(n²) 的总时间复杂度

于 2015-07-22T14:27:32.690 回答