问8T(n/2) +n^2的树形算法

EN

不幸的是，@vahidreza的解决方案在我看来是错误的，因为它与Master定理相矛盾。根据主定理a = 8，b = 2，c = 2。因此，这是一个由子问题主导的递归，所以答案应该是T(n) = Ө(n^3)，而不是@ O(m^(2+1/3))。

主要问题可能在以下语句中：

你也知道，这棵树有m个log_8级。因为在每个级别上，您将数字除以8。

让我们试着正确地解决它：

• 在第0级您有n^2 (我更喜欢从0开始计数，因为它稍微简化了表示法)
• 在第一级您有8节点D21或总计8*(n/2)^2
• on第二级您有<代码>D21或总计8*(n/2)^2
• on的8 * 8节点<代码>D25第-级您有<代码>D27的节点或总计<代码>D28=<代码>D29= 8^2*(n/(2^2))^2
• on

在每个级别上，您的值n除以2，因此在级别i上，值为n/2^i，因此您将拥有log_2(n)级别。所以你需要计算的是i从0到log_2(n) of n^2 * 2^i的和。这是一个与2之比的几何级数，所以它的和是

Σ (n^2 * 2^i) = n^2 * Σ(2^i) = n^2 * (2^(log_2(n)+1) - 1)/2

因为我们讨论的是Ө/O，所以我们可以忽略常量，所以我们需要估计

n^2 * 2^log_2(n)

显然，2^log_2(n)就是n，所以答案是

T(n) = Ө(n^3)

正如大师定理所预言的那样。