已知算法A运行时间函数为T（n）=8T（n 2）+n2，其中n表示问题规模，则该算法时间复杂度为（ ）
展开全部
【答案】：D
我们可以假设这个函数为Q(n)=a*n^3+b*n^2+c*n+d(我们假设是一个幂函数，最高次数是三次，假设成什么都可以，但是假设为幂函数大家好理解。)然后将式子带入得a*(2n)^3+b*(2n)^2+c*(2n)+d=2(a*n^3+b*n^2+c*n+d),然后展开，发现式子会变成这样：8a*n^3+4b*n^2+2c*n+d=2a*n^3+2b*n^2+2c*n+2d。对于一个多项式来说，如果等式两边相等，那么每一项（幂数相同，式子中a、b、c、d均为系数)都应该相同那么应该：8a*n^3=2a*n^3、4b*n^2=2b*n^2、2c*n=2c*n、d=2d。很明显如果等式想要相等话，那么式子中三次项、二次项、常数项系数应为0所以这个式子就会变为2c*n,所以Q(n)=2c*n，因为2c为常数，所以可以省去。这个函数就是一个线性函数，Q(n)=n,然后在将式子回带，Q(n)=n，那么G(n)=n-1,依旧是线性函数，省略1，此时G(n)=n，那么T(n)=n^3,所以时间复杂度为n^3
我们可以假设这个函数为Q(n)=a*n^3+b*n^2+c*n+d(我们假设是一个幂函数，最高次数是三次，假设成什么都可以，但是假设为幂函数大家好理解。)然后将式子带入得a*(2n)^3+b*(2n)^2+c*(2n)+d=2(a*n^3+b*n^2+c*n+d),然后展开，发现式子会变成这样：8a*n^3+4b*n^2+2c*n+d=2a*n^3+2b*n^2+2c*n+2d。对于一个多项式来说，如果等式两边相等，那么每一项（幂数相同，式子中a、b、c、d均为系数)都应该相同那么应该：8a*n^3=2a*n^3、4b*n^2=2b*n^2、2c*n=2c*n、d=2d。很明显如果等式想要相等话，那么式子中三次项、二次项、常数项系数应为0所以这个式子就会变为2c*n,所以Q(n)=2c*n，因为2c为常数，所以可以省去。这个函数就是一个线性函数，Q(n)=n,然后在将式子回带，Q(n)=n，那么G(n)=n-1,依旧是线性函数，省略1，此时G(n)=n，那么T(n)=n^3,所以时间复杂度为n^3
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
