安德鲁算法的时间复杂度（复壳）

Question

根据Wikibooks，如果所有点都已排序，安德鲁算法将以线性时间运行。我们将以排序点为例。

然而，在伪代码中它说：

for i = 1, 2, ..., n:
while L contains at least two points and the sequence of last two points
        of L and the point P[i] does not make a counter-clockwise turn:
    remove the last point from L
append P[i] to L

现在，在这里我们可以看到一个for循环和一个嵌套在for循环内的while循环。按照我的逻辑推理，如果一个循环里面还有一个循环，那么时间复杂度根本不可能是线性的。

我哪里出错了？谢谢！

编辑：通过分析代码，我推断出以下内容。

for i loop--------O(n)
    while loop----O(i-2) worst case
        remove----O(1)
    append--------O(1)

现在，如果 while 循环的时间复杂度为 O(n)，则整体复杂度为 O(n^2)。但是因为比较小，整体复杂度应该是O((i-2) * n)，我觉得比O(n)大，因为i递增到n...

我不太确定如何正确计算...

Answer 1

嗯，你确实有线性复杂度，因为：

For (i=1 ... n) 为复杂度提供了一个 n 因子，所以直到现在 O(n)

在嵌套的 while 循环中，你有条件（L size >= 2 && 它还会检查你是否逆时针转动（应该在恒定时间内完成））。因此，这似乎也可以将复杂度缩放到 n 的一个因子（这将产生二次复杂度 O(n*n)）

但现在问题是嵌套的while循环体最多可以执行N次，因为你从L中弹出元素；并且除了每个 i 一次外，您不会将 L 中的元素推入。因此，在算法的执行过程中，push(append) 语句将恰好执行 N 次，因此 POP（删除最后一个元素）最多可以执行 N 次，而不管它是否嵌套在封闭的 for 循环中。因此，复杂度仍然是 O(n) = 线性复杂度。

安德鲁算法的时间复杂度（复壳）

Time complexity of Andrew's algorithm (complex hull)

algorithm

time-complexity

convex-hull