3

这个问题已经回答了，但我面临的主要问题是理解其中一个答案。

来自 https://stackoverflow.com/a/1621913/2673063

以下算法如何O(n)？

它指出，如果需要，首先对点进行排序/计算凸包（在 O(n log n) 时间内），我们可以假设我们有凸多边形/包，其中的点按照它们在多边形中出现的顺序循环排序。调用点 1, 2, 3, ... , n。让（变量）点 A、B 和 C，分别从 1、2 和 3 开始（按循环顺序）。我们将移动 A、B、C 直到 ABC 是最大面积三角形。（这个想法类似于计算直径（最远对）时使用的旋转卡尺方法。）

在 A 和 B 固定的情况下，只要三角形的面积增加，则前进 C（例如，最初，A=1，B=2，C 前进到 C=3，C=4，……），即只要面积(A,B,C) ≤ 面积(A,B,C+1)。对于那些固定的 A 和 B，这个点 C 将是最大化 Area(ABC) 的点。（换句话说，函数 Area(ABC) 作为 C 的函数是单峰的。）

接下来，如果增加了面积，则推进 B（不改变 A 和 C）。如果是这样，再次如上所述推进C。如果可能，然后再次推进 B，等等。这将给出以 A 作为顶点之一的最大面积三角形。（到这里的部分应该很容易证明，简单地对每个 A 单独执行此操作将得到 O(n2)。但请继续阅读。）现在再次推进 A，如果它改善了面积等。虽然这有三个“嵌套”循环，注意 B 和 C 总是“向前”前进，它们总共最多前进 2n 次（类似 A 最多前进 n 次），所以整个事情在 O(n) 时间内运行。

4

2 回答 2

3

作为问题主题的答案的作者，我觉得有必要对O(n)运行时进行更详细的解释。

首先，作为一个例子，这里有一张来自论文的图，显示了算法的前几个步骤，用于特定的样本输入（12 边形）。首先我们从A、B、C三个连续的顶点开始（图中的步骤1），只要面积增加就推进C（步骤2到6），然后推进B，以此类推。

样品运行

上面带有星号的三角形是“锚定的局部最大值”，即最适合给定 A 的三角形（即，推进 C 或 B 会减小面积）。

就运行时而言O(n)：让 B 的“实际”值，根据它被增加的次数并忽略环绕，是 nB，同样对于 C 是 nC。（换句话说，B = nB % n和C = nC % n。）现在，请注意，

  1. （“B 领先于 A”）无论 A 的值是多少，我们都有 A ≤ nB < A + n

  2. nB 一直在增加

因此，当 A 从 0 变化到 n 时，我们知道 nB 仅在 0 和 2n 之间变化：它最多可以增加 2n 次。同样 nC。这表明算法的运行时间，与 A、B 和 C 递增的总次数成正比，以 O(n) + O(2n) + O(2n) 为界，即 O(n ）。

于 2013-08-26T12:00:04.080 回答
0

可以这样想：每个A, B, C都是指针，在任何给定时刻，都指向凸包的元素之一。由于算法递增它们的方式，它们中的每一个将最多指向凸包的每个元素一次。因此，每一个都将迭代一组O(n)元素。它们永远不会被重置，一旦它们中的一个传递了一个元素，它就不会再传递那个元素了。

因为有 3 个指针 ( A, B, C)，所以我们有时间复杂度3 * O(n) = O(n)。

编辑：

由于代码显示在提供的链接中，听起来它可能不是O(n)，因为B和C环绕数组。但是，根据描述，这种环绕听起来没有必要：在看到代码之前，我想象该方法停止了B和C过去的进展n。那样的话，肯定是O(n)。但是，由于提供了代码，我不确定。

出于某种数学原因，它可能仍然是这样，B并且在整个算法中C仍然只迭代O(n)几次，但我无法证明这一点。我也不能证明不回绕是正确的（只要您处理索引越界错误）。

于 2013-08-24T21:18:59.183 回答