首页
登录
从业资格
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
最全题库
2022-08-02
59
问题
某个算法的时间复杂度递归式 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.系
随机试题
WhatwasthepriceofabarrelofcrudeoilonFriday?[originaltext]Higher
Whatdidthemandoduringthewintervocation?[br][originaltext]M:Didyoud
[originaltext]W:We’vealreadyboughtanoven,awashingmachine,adishwasher,
读下图,完成下题。 甲地()。A.位于印度河平原 B.全年高温多雨
以下哪项不能作为巨幼细胞性贫血骨髓检查的诊断依据A.中性粒细胞核分叶过多B.白细
特殊巡视指因设备运行环境变化而开展的巡视。()
在前期建筑策划中应考虑的相关因素包括( )。A.建筑造价 B.建筑法规 C
下列关于我国金融资产管理公司的说法,错误的是( )。A.我国四家金融资产管理公司
车辆损失险的保险金额的确定可以按车辆的新车购置价或实际价值确定,也可( )。A
水泥土搅拌桩地基,深层搅拌法的特点是()A.振动大 B.设计灵活 C.对土无
最新回复
(
0
)