運行時解釋

Question

有人可以向我解釋爲什麼這個算法的遞歸部分有運行時間，如果n≤3，T（n）= {O（1） （n/2）表示T（n/2）的底部函數，其中Tf（n/2）表示Tf（n/2）+ Tc（n/2）+ O和Tc（n/2）代表頂替功能

的算法稱爲Shamos和主要步驟是：

1. 如果N≤3找到強力的最接近點和止損。
2. 找到一條垂直線V，以便將輸入集合劃分爲兩個大小爲 的不相交子集PL和PR，並儘可能相等。指向左邊或在行 屬於PL，並且指向右邊或在行上屬於PR。因爲 集合是不相交的，所以沒有一點屬於兩者。
3. 遞歸地找到PL中最近對點的距離δL和PR中最接近的一對 的距離δR。

4. 設δ= min（δL，δR）。輸入集P中的一對最近點的距離是在遞歸步驟中找到的點（即，δ）的 或者由PL 中的點與PR中的點之間的距離組成。

   （a）唯一的候選人指出一個來自PL，而來自PR的唯一候選人必須位於距離線V左邊的距離爲δ的一條線的一條豎線條 中，並且距離V右邊的距離δ處的線（b）設YV是由不減少的y座標 （即，如果i≤j則YV [i]≤YV[j]）排序的條帶內的點的陣列。 （c）從YV中的第一個點開始，除了最後一個步驟之外，檢查該點的距離 以及接下來的7個點（或者如果不多於7個，則剩下任何剩餘的點）。如果發現一對 對的距離嚴格小於δ，則將此距離分配給δ。

5. 返回δ。 預先感謝您。

Answer 1

T(c(n/2))和T(f(n/2))描述它需要多少時間分別遞歸調用該算法上的左右兩組，自從點的一半已經被放置在每個小組。

O(n)來自算法的棘手部分：在遞歸調用之後，我們找到了δ，即左邊組或右邊組中最接近的一對點之間的距離。現在我們要查找由左邊一個點和右邊一個點組成的對。當然，從中線看距離δ更遠的點幾乎沒有用處。然而，它仍然可能是所有點都在中間線的δ內，所以看起來我們冒險必須比較n^2點對。現在重要的觀察結果是，正是因爲我們知道在每個組中，沒有一對點比δ更接近，我們知道對於需要查看的右側組有多少點存在小的，持續的最壞情況限制對於左側組中的每一對。所以如果我們只能得到我們的點在他們的y座標上排序，我們可以在線性時間內找到最接近的點。由於列表在遞歸調用之間傳遞的方式，可以在線性時間內獲得這個排序列表，但細節可以逃脫我（隨意填寫，任何人）。