凸壳中最大的三角形
问题已经得到解答，但我面临的主要问题是理解其中一个答案。
来自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）。 这个点C将是那些固定A和B最大化区域（ABC）的点。（换句话说，函数Area（ABC）是C的函数的单峰）。）
接下来，如果增加面积，则前进B（不改变A和C）。 如果是这样，再次按上述方式推进C. 然后如果可能的话再次前进B等。这将给出最大区域三角形，其中A作为顶点之一。 （到这里的部分应该很容易certificate，并且简单地为每个A单独执行此操作将给出O（n2）。但请继续阅读。）现在再次推进A，如果它改善了面积等，虽然这有三个“嵌套的“循环，请注意B和C总是前进”，并且它们总共最多前进2n次（类似A最多前进n次），因此整个过程在O（n）时间内运行。
作为问题主题的答案的作者，我觉得有必要对O(n)运行时给出更详细的解释。
首先，作为一个例子，这里是一篇文章，显示了算法的前几个步骤，对于特定的样本输入（12-gon）。 首先，我们从A，B，C开始作为三个连续的顶点（图中的步骤1），只要面积增加（步骤2到6）就前进C，然后前进B，依此类推。
在它们上方带有星号的三角形是“锚定的局部最大值”，即对于给定的A最佳的三角形（即，推进C或B将减小该区域）。
只要运行时为O(n) ：让B的“实际”值按其增加的次数而忽略环绕，为nB，类似地，C为nC。 （换句话说， B = nB % n和C = nC % n 。）现在，请注意，
因此，当A从0到n变化时，我们知道nB仅在0和2n之间变化：它可以最多增加2n次。 同样nC。 这表明算法的运行时间与A，B和C的总次数成正比，由O（n）+ O（2n）+ O（2n）限定，即O（n） ）。
可以这样考虑： A, B, C中的每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)次，但我无法certificate这一点。 我也不能certificate不回滚是正确的（只要你处理索引越界错误）。