首页
登录
从业资格
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
某个算法的时间复杂度递归式 T(n)=T(n-1)+n ,其中 n 为问题的规模
最全题库
2022-08-02
60
问题
某个算法的时间复杂度递归式 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.系
随机试题
Theteachernotifiedusthattheexaminationwouldbeheldin______.A、twoweeks
ManyAmericanwomenareearningmoneyoutsidetheirhomestoday.Amongwomen
[originaltext]Areyoufamiliarwithlargesupermarkets?Ifso,thenyoupro
JustlikeChinese,Westernersgivegiftsonmanyoccasions,suchas,onbirt
以下关于土地侵权纠纷处理的表述中,正确的有( )。A.土地侵权纠纷可以采取协商
甲公募基金管理公司在发售某基金产品的过程中,为提高基金募集规模,对其直销客户采用
基金管理人应当自收到投资者的申购(认购)、赎回申请之日起()个工作日内,对该申
以下项目应在资产负债表上银行存款余额中做出处理的是()。A.决算日下午上班时仍未
对主滑段滑床及地表坡面较平缓,前缘有较多地下水渗出的浅层土质滑坡最宜采用下列()
某企业2020年年初拥有排气量2.8升的乘用车1辆(核定载客人数9
最新回复
(
0
)