首页
登录
从业资格
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
最全题库
2022-08-02
58
问题
某个算法的时间复杂度递归式 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 倍。
转载请注明原文地址:https://tihaiku.com/congyezige/2408345.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某项目包含的活动如下表所示,完成整个项目的最短时间为(请作答此空)周。不能通过缩
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
以下不属于自动化测试的局限性的是( )。A.周期很短的项目没有足够时间准备测试
某开发小组为某企业开发较大规模的项目,该开发小组已经为同一行业的其他企业开发过类
有两个N*N的矩阵A和B,想要在微机(PC机)上按矩阵乘法基本算法编程实现计
采用插入排序算法对n个整数排序,其基本思想是:在插入第i个整数时,前i-1个整数
在软件开发过程中,详细设计的内容不包括( )设计。A.软件体系结构 B.算法
以下属于影响软件可靠性因素的是( )。 ①软件运行剖面②软件规模
以下属于静态测试方法的是( )。A.分支覆盖率分析 B.复杂度分析 C.系
随机试题
Aestheticsisthatregioninthelandofsciencewhosebordersofinvestiga
在Authorware中,关于移动图标的说法中错误的是()。A.移动图标只能移动
粘性土的状态可分为坚硬、硬塑、可塑、软塑、流塑,划分的根据是土的()。A.密
试回答以下交通标志外观质量检查的问题。(1)外观质量包括()。A.缺陷检查
公路隧道按长度分类,短隧道的划分标准为()。A:L>3000m B:3000
A.累及主动脉的升弓降部,占病例的70% B.累及升主动脉,占病例的5% C
患者,女,26岁。经前腹痛剧烈,拒按,经色紫黑,有血块,血块下后疼痛缓解。治疗应
房地产估价方法主要有市场法、成本法、收益法、假设开发法、长期趋势法、基准地价修正
关于提高混凝土抗变形性能,以下说法正确的是()。A.变形控制主要包括对干缩变形
30岁男性农民,腹痛、腹泻半个月,大便4~8次/天,便量多,为暗红色,有腥臭味,
最新回复
(
0
)