algorithm - 安德鲁算法的时间复杂度(复壳)

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

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

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