首页
登录
从业资格
已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ,其中 n 表示
已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ,其中 n 表示
题库
2022-08-02
53
问题
已知算法 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
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
计算机中CPU的中断响应时间指的是()的时间。A.从发出中断请求到中断处理结束
MPEG视频中的时间冗余信息可以采用()的方法来进行压缩编码。A.帧间预测和变
计算机运行过程中,遇到突发事件,要求CPU暂时停止正在运行的程序,转去为突发事件
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
在数据库系统运行维护阶段,通过重建视图能够实现()A.程序的逻辑独立性 B.
数据库应用系统在运行过程中,发现随着数据量的不断增加,有部分查询业务和数据更新业
某项目包含的活动如下表所示,完成整个项目的最短时间为(请作答此空)周。不能通过缩
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
在C程序中,对于如下的两个for语句,其运行后a和b的值分别为( )。 fo
随机试题
[originaltext]W:Oh,[12]rmfedupwithmyjob.M:Hey,thereisaperfectjob
TheAmericanIndians——ApeopleinCrisisIndianslivedinNor
信不信我是你自己的事。Itisyourconcernwhetheryoubelievemeornot.
[originaltext]W:Airsecuritychecksintheairportalwaysmakemenervous.I’m
高中历史《年轻的反叛者——列宁》 二、考题解析 【教学过程】
A.茵陈连翘 B.茵陈炮姜 C.青蒿栀子 D.青蒿桂枝
下列不属于股权投资母基金的业务的是( )。A.一级投资 B.二级投资 C.
患者,男性,41岁,严重脑外伤。护士收集资料、评估患者、制定护理计划。该计划中,
A公司由张三和李四在国外的某小岛注册成立,总部位于杭州,A公司从事互联网业务,在
关于明洞回填施工要求的说法,正确的是()。A.明洞两侧回填水平宽度小于1.2
最新回复
(
0
)