首页
登录
从业资格
已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ,其中 n 表示
已知算法 A 的运行时间函数为 T(n)=8T(n/2)+n2 ,其中 n 表示
题库
2022-08-02
54
问题
已知算法 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
随机试题
Accordingtothispassage,yourintelligenceprobably______.[br]Onepossible
Whatisthelecturemainlyabout?[br]Whatistheinitialstageofmemorycalle
Whatistheconversationmainlyabout?[br][originaltext]W:Doyoulikesports
胆道出血、感染时,胆汁回声强度变化规律错误的是A.感染的胆汁可出现回声 B.混
突起路标固定于路面上,可独立使用或配合标线使用。请根据有关知识和标准回答下列问题
阅读关于“中国气候”的图文材料,按要求完成教学设计任务。 材料一《义务教育地
关于资产可收回金额的计量,下列说法中正确的有( )A.可收回金额应当根据资产的
各层次的教育目的中,既由特定社会领域和特定社会层次的需要所决定,也因受教育者所处
牙周膜的主要成分是A、胶原纤维 B、上皮剩余 C、成骨细胞 D、破骨细胞
A.为了早期发现、早期诊断、早期治疗乳腺癌 B.为了调查大学生乙型肝炎感染情况
最新回复
(
0
)