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 % nC = 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),因为BC环绕数组。但是,根据描述,这种环绕听起来没有必要:在看到代码之前,我想象该方法停止了BC过去的进展n。那样的话,肯定是O(n)。但是,由于提供了代码,我不确定。

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

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