recurrence - 重复关系工作

Question

我正在写一篇数据结构和算法论文，其中正在教授递归关系。

问题如下：

根据我对这个问题的理解，n 将一次又一次地减半。所以剩下的就是 1/32n^2 + 1/16n^2 + 1/8n^2 + 1/4n^2 + 1/2n^2 + n^2。所有分数总和为 1。所以你剩下 n^2 +n^2 = 2n^2。

然而，这不是一个可能的解决方案。

有人可以帮助我理解如何正确计算这些递推关系，或者指出我正确的方向，因为我在这个主题上遇到了很多麻烦，非常感谢任何帮助。

感谢您的时间。

Answer 1

你可能想看看主定理

在 wiki 中，a = 1, b = 2, c = 2，其中 T(n) = aT(n/b) + n^c

案例 3 适用，因为 2 > 0 = log_2(1)

因此，根据主定理，T = Big-Theta(n^c) = Big_Theta(n^2)。

选项 B 有一个 ^2 项，所以这应该是您的答案。