安德魯算法（複雜船體）的時間複雜度

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）=線性複雜度。