分析复杂

我被要求使用迭代方法来分析下面的递归公式的时间复杂度：分析复杂

T（N）= T（N/3）+ T（2n个/ 3）+ N^2。

T（1）= 1

当我尝试展开它炸毁方程，我真的不能跟踪所有的递归“呼吁”和常量。这是由于数据分割不均（1 \ 3 - 2 \ 3）造成的。

有没有更简单的方法来解决这个使用迭代方法？

非常感谢。

来源

2013-03-20 Paz

您可以使用Akra-Bazzi方法先找到解决方案。 – 2013-03-20 12:14:08

您是否试过谷歌搜索这个确切的方程？ – jamylak 2013-03-20 12:43:12

什么是'T（0）'？ 0？ – Claudiu 2013-03-20 15:07:05

这似乎是为O（n^2）如果我没有错过任何东西......

所有T首先单调增长（数第一值，您可以手动检查这一点，它是由剩下的归纳 - 如果函数在[1..10]中单调，那么它将在[1..15]等单调）。

T(n)=T(n/3)+T(2n/3)+n^2<=2T(2n/3)+n^2 
T(n)<=n^2+2*(2n/3)^2+4*(4n/9)^2+... 
    =sum[k=0..log3(n)]((8/9)^k*n^2) 
    =n^2*sum[k=0..log3(n)](8/9)^k 
    <=n^2*sum[k=0..inf](8/9)^k 
    <=C*n^2

来源

2013-03-20 14:13:28 maxim1000

我对这个有点新，但是，我们可以总是假设大部分需要比小部分更长吗？（我看你用2T（2n/3）的上界来界定原始序列） – Paz 2013-03-20 15:27:03

@ user2190298：我已经添加了关于单调性的解释，是否清楚？ – maxim1000 2013-03-20 15:46:49

是的。水晶。谢谢！ – Paz 2013-03-21 18:44:05

Here是纸示出一个类似的公式的分析：T（N）= T（N/3）+ T（2π/ 3）+ N

的一种方法，使其迭代将需要使用与解析器\编译器工作方式相似的方法

应用公式：T（n）= T（n/3）+ T（2n/3）+ n^2 n = 1..9

T(0) = 0 

T(1) = T(1/3) + T(2/3) + 1 

T(2) = T(2/3) + T(4/3) + 4 

T(3) = T(1) + T(2) + 9 

T(4) = T(4/3) + T(8/3) + 16 

T(5) = T(5/3) + T(10/3) + 25 

T(6) = T(2) + T(4) + 36 

T(7) = T(7/3) + T(14/3) + 49 

T(8) = T(8/3) + T(16/3) + 64 

T(9) = T(3) + T(6) + 91 

T(3m) = T(m) + T(2m) + 9m^2

..也许这可以给你一些提示

来源

2013-03-20 14:46:46

这里有什么有用的是不要乘以任何数字，而是用权力来写所有的东西。这样做，全部由手工，我得到了最初的几个扩展如下：

T(n) = T((1/3)n) + T((2/3)n) + n^2 
    = T((1/3^2)n) 
     + 2T((2/3^2)n) 
     + T((2^2/3^2)n) 
     + [n^2]      #constants from the first expansion 
     + [((1/3)n)^2 + ((2/3)n)^2] #constants from the second expansion 
    = T((1/3^3)n) 
     + 3T((2/3^3)n) 
     + 3T((2^2/3^3)n) 
     + T((2^3/3^3)n) 
     + [n^2] 
     + [((1/3)n)^2 + ((2/3)n)^2] 
     + [((1/3^2)n)^2 + ((2/3^2)n)^2 + ((2^2/3^2)n)^2] #constants from 3rd expansion

这是一个有点难以启齿，但似乎什么发生的是，你得到的二项式系数会为T s，其中的x次扩张看起来是这样的：

T(n) = sum((x choose i) * T(((2^i)/(3^x))n), i from 0 to x) 
     + constants

在每一步中，都在扩张x增加的附加常数是从扩张x-1的参数T，平方，因为他们都最终获得方感谢n^2。因此，所有的新常数在给定的扩张y等于：

NewConsts(y) = sum(((y - 1) choose i) * (((2^i)/(3^(y-1)))*n)^2, i from 0 to y - 1)

而且所有常量在扩张x等于

n^2 + sum(NewConsts(y), y from 1 to x)

因此，假设上述所有被正确，我不是100％确定的，我猜你必须弄清楚常数何时停止提供 - 也就是说，x是((2^x/3^x) * n)^2)等于0 - 你的答案是所有这些常数的总和。

来源

2013-03-20 15:14:56 Claudiu

回答

相关问题