廣場地形復發推導

Question

你有一個方形的地形與地域的A> 0。你想添加信息到地形。您想將地形細分爲4個象限，分別處理它們，並彙總結果。到過程中，把一個象限進一步直到子象限具有面積< = A0，其中然後可以將信息添加到所有的地形中總的我* A對於i> 0。每個細分步驟產生時間中的每個的四個象限包含1/3的面積。如果T（A）是標記A區地形的時間，那麼它的重現是什麼？

我有一個答案爲4T（（A/A0）/ 3）+ IA，但我不明白它是如何衍生的。有人可以解釋問題的每個組成部分是如何與最終結果相加的？我理解4次遞歸調用，但在此之後不多。

Answer 1

如果T(A）爲標記區域的地形時A然後讓計算T(A)遞歸：

• 當分析A的面積比A0（A <= A0小於或等於），那麼我們有T(A) = c對於一些常數c，因爲我們不再細分。從你的說法，我認爲我們可以假設，T(A) = i*A (if A <= A0)

• 當區域A比A0更大然後我們首先將A到區域A/3每個，對它們進行處理的四個子象限，最後聚集在地形的所有信息，從而T(A) = 4*T(A/3) + i*A (if A > A0)

因而最終復發可被寫爲：

T(A) = i*A    (A <= A0) 
T(A) = 4*T(A/3) + i*A (A > A0) 

注：我認爲，你給T(A) = 4*T((A/A0)/3) + i*A公式是不完全正確的，因爲你會被除以3*A0A可以比3大得多。 A0只是用於治療爲其子象限面積比A0較小的情況下。