在凸包

Question

最大三角形的問題已經回答了，但我現在面臨的主要問題是在理解一個答案..

從 https://stackoverflow.com/a/1621913/2673063

如何算法O(n)以下？通過首先對點/計算凸包（在O（n log n）時間內）進行排序（如果有必要），我們可以假設我們有凸多邊形/船體，點以它們的順序循環排序出現在多邊形中。調用點1,2,3 ...，n。讓（可變的）點A，B和C分別以1,2和3開始（以循環順序）。我們將移動A，B，C直到ABC是最大面積三角形。 （這個想法類似於計算直徑（最遠對）時使用的旋轉卡尺方法。）在A和B固定的情況下，前進C（例如最初，其中A = 1，B = 2，C是隻要區域（A，B，C）≤區域（A，B，C + 1），只要三角形的面積增加，即通過C = 3，C = 4，...）。此點C將是那些使固定的A和B的面積（ABC）最大化的點（換句話說，作爲C的函數，功能面積（ABC）是單峯的。）改變A和C），如果這增加了面積。如果是這樣，再次推進C如上。如果可能，再次提前B等。這將給出與A最大的區域三角形作爲其中一個頂點。 （到這裏的部分應該很容易證明，並且簡單地爲每個A單獨做這個會給O（n2），但繼續閱讀。）現在再次提前A，如果它改善了面積等等。 雖然這有三個「嵌套」循環，注意B和C總是前進，並且它們總共最多前進2n次（同樣A最多前進n次），所以整個事件都運行在O（n）時間。

Answer 1

作爲該問題的主題the answer的作者，我覺得有必要對O(n)運行時作出更詳細的解釋。

---

首先，只是作爲一個例子，這裏是從紙張的圖，示出了算法的前幾個步驟，對於特定的樣品輸入（12邊形）。首先我們以A，B，C三個連續頂點（圖中的第一步）開始，只要區域增加（步驟2到6），則前進C，然後前進B，等等。

與它們上方的星號三角形是「錨定的局部最大值」，即，最適合於一個給定的A（即，前進無論是C或B將降低的區域）的人。

---

至於運行時間爲O(n)：讓B的「實際」值，在次數方面，它一直在遞增，各地無視包裹，是NB，同樣對C是NC。 （換句話說，B = nB % n和C = nC % n）。現在，請注意，

1. （ 「B超前A的」）A的任何價值，我們有一個≤ NB < A + N

2. NB總是增加

所以，作爲一個從0到n變化，我們知道，只有NB 0和2N之間變化：它可以在最2n倍遞增。類似nC。這表明算法的運行時間與O（n）+ O（2n）+ O（2n）成正比，其與A，B和C的總次數成正比，其爲O ）。

Answer 2

想想這樣：A, B, C中的每一個都是指針，在任何給定的時刻，它指向凸包中的一個元素。由於算法增加它們的方式，它們中的每一個最多隻會指向凸包的每個元素一次。因此，每個元素將迭代一組O(n)元素。他們永遠不會被重置，一旦他們中的一個已經通過一個元素，它不會再次通過該元素。

由於有3個指針（A, B, C），所以我們有時間複雜度3 * O(n) = O(n)。

編輯：

由於代碼在所提供的鏈接呈現，這聽起來可能的，它是不O(n)，由於陣列周圍B和C包裹物。然而，根據描述，這種包裝並不是必須的：在看到代碼之前，我想到了阻止B和C過去n的進步的方法。在那種情況下，肯定會是O(n)。由於代碼呈現，但我不確定。

由於某些數學原因，B和C仍然只能在整個算法中迭代O(n)次，但我不能證明這一點。我也不能證明不環繞它是正確的（只要你處理索引越界錯誤）。