首页
登录
从业资格
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
最全题库
2022-08-02
21
问题
某个算法的时间复杂度递归式 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.系
随机试题
Nosoonershecanreceivethesumofmoneythanshecameupwithanideaofhow
[originaltext]M:Idon’tenjoydatinganymore.Ican’tseemtofindanyoneIha
[originaltext]Manisalandanimal,butheisalsocloselytiedtothesea.Thr
莎士比亚的四大悲剧是()。A.《哈姆雷特》 B.《李尔王》 C.《奥赛
走、跑、跳、投掷、钻爬是指体能的哪一方面?( )A.生理机能 B.身体基本活
下列不属于反映被投资企业管理状况的指标是()。A.股东关系与公司治理 B
从所给的四个选项中,选择最合适的一项填入问号1和问号2处,使之呈现一定的规律性:
法律风险与违规风险之间的关系是()。A.违规风险包括法律风险 B.两者产
下列关于《个人信用信息基础数据库管理暂行办法》的说法,错误的是()。A.明确
粪胆原减少见于A.肠道炎症 B.溶血性黄疸 C.急性白血病 D.阻塞性黄疸
最新回复
(
0
)