2. 从业资格
  3. 已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ，其中 n 表示

已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ，其中 n 表示

题库2022-08-02  62
问题 已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ，其中 n 表示问题的规模，则该算法的时间复杂度为（）A.θ(n)B.θ(nlgn)C.θ(n2)D.θ(n3)
选项 A.θ(n)
B.θ(nlgn)
C.θ(n2)
D.θ(n3)
答案 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
转载请注明原文地址:https://tihaiku.com/congyezige/2408382.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)