0

您有一个面积为 A > 0 的方形地形。您想将信息添加到地形中。您想将地形细分为 4 个象限，分别处理它们并组合结果。要进行处理，您需要进一步划分一个象限，直到子象限的面积 <= A0，然后您可以在其中向地形添加信息 - 对于 i > 0，总共需要 i*A 时间。每个细分步骤都会导致每个四个象限包含 1/3 的面积。如果 T(A) 是标记区域 A 的地形的时间，它的循环是多少？

我的答案是 4T((A/A0)/3)+iA，但我不明白它是如何得出的。有人可以解释问题的每个组成部分如何与最终结果中的添加相关吗？我了解 4 个递归调用，但在那之后就不多说了。

4

1 回答 1

0

如果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并不完全正确，因为您将除以A可以3*A0比 大得多3。A0仅用于处理子象限面积小于 的情况A0。

于 2013-02-28T11:08:34.513 回答