0

我想证明从给定的一组点（2D）构造一个简单多边形的问题的复杂性至少是O(n logn) ，即每个正确的算法至少需要 O(n logn) 步骤来解决这个问题最坏情况下的问题。是否有可能以某种方式将此问题简化为排序问题，或者如何显示？

4

2 回答 2

2

是的，使用基线算法：

在此处输入图像描述

  • 找到具有最低和最高 x 值的两个点：O(n)
  • 将位于基线上方和下方的其他点分成两组（连接这些点的线）：O(n)
  • 按“升序 y/升序 x”排序上集：O(n*logn)
  • 按“降序 y/降序 x”排序较低的集合：O(n*logn)
  • 按顺序加入上层集合，按顺序加入下层集合：O(n)
于 2013-06-16T12:03:27.433 回答
2

是的，可以通过将其与排序问题进行比较来证明它，但你必须反过来减少它。也就是说，在 O(n) 时间内将排序问题简化为多边形构造问题。

于 2013-06-16T12:06:29.053 回答