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

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 中弹出元素；并且您不会在 L 中推送元素，除了每个 i 一次。因此，在算法的执行过程中，push(append) 语句将精确执行 N 次，因此 POP(删除最后一个元素)最多可以执行 N 次，而不管它嵌套在封闭的 for 循环中。因此，复杂度仍然是 O(n) = 线性复杂度。