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

Question

根据Wikibooks，如果所有点已经排序，Andrew算法将以线性时间运行。我们将采取排序积分的情况。

然而，在伪代码，它说：

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）大，因为我增加到n ...

我不太确定正确计算这个...

Answer 1

那么你必须线性复杂，因为：

对于（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）=线性复杂度。