首页
登录
从业资格
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
练习题库
2022-08-02
83
问题
某个算法的时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为(请作答此空 ),若问题的规模增加了16倍,则运行时间增加()倍。A.O(n)B.O(nlgn)C.O(n2)D.O(n2lgn)
选项
A.O(n)
B.O(nlgn)
C.O(n2)
D.O(n2lgn)
答案
C
解析
对于递归式,假设T(1)=1,则:T(n)=T(n-1)+n=T(n-2)+n-1+n=T(n-3)+n-2+n-1+n=1+2+…+n-1+n=n(n+1)/2可见,时间复杂度为O(n2)。若问题的规模增加了16倍,则运行时间增加了162=256倍。
转载请注明原文地址:http://tihaiku.com/congyezige/2408405.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是t取指=2
中断响应时间是指()。A.从中断处理开始到中断处理结束所用的时间 B.从发出
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
甲、乙两人在同一时间就同样的发明创造提交了专利申请,专利局将分别向各申请人通报有
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
某开发小组为某企业开发较大规模的项目,该开发小组已经为同一行业的其他企业开发过类
某系统中,模块A处理与销售相关的所有细节,仅需要发送一个包含销售量、价格和时间的
以下关于模块化的叙述中,正确的是( )。A.每个模块的规模越小越好,这样开发每
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
随机试题
ThepoemIsabellawaswrittenby______.A、ShellyB、ByronC、WordsworthD、KeatsD
李先生打算为刚上小学的儿子筹备大一的开支。他准备采用教育储蓄的方式进行。为此,他
能治疗白癫风的药是A.补骨脂 B.菟丝子 C.杜仲 D.续断 E.骨碎补
调摄精神属于A.治病求本B.既病防变C.未病先防D.因地制宜E.因时制宜
统计最基本的职能是( )A.信息职能 B.咨询职能 C.监督职能 D.预测
根据中华人民共和国2016年国民经济和社会发展统计公报公布的数据显示,2016年
根据合同法律理论,同时具有双务、有偿和诺成性质的合同有( )。A.承揽合同 B
男,65岁。活动时心悸、气短1年余。查体:胸骨左缘第3肋间可闻及舒张期叹气样杂音
男性,52岁,反复无痛性肉眼血尿伴条状血块2月,膀胱镜检见右输尿管口喷血,尿细胞
属于施工质量控制依据中专业技术性依据的有()。A.国家和政府有关部门颁布的与质
最新回复
(
0
)