首页
登录
从业资格
在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
考试题库
2022-08-02
48
问题
在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算法的渐进时间复杂度为( ),若问题的规模增加了16倍,则运行时间增加( )倍。问题1选项A.Θ(n)B.Θ(nlgn)C.Θ(n2)D.Θ(n2lgn)问题2选项A.16B.64C.256D.1024
选项
答案
CC
解析
由于递归式为:T(n)=T(n-1)+n。我们可以把一个规模为n的时间复杂度算出来。
分析过程为:
T(n)=T(n-1)+n;
T(n-1)=T(n-2)+n-1;
T(n-2)=T(n-3)+n-2;
....
T(n)=1+2+..+n-1+n。
这是一个典型的等差数列。用数列求和公式有:((1+n)*n)/2。这样就求得时间复杂度为:Θ(n2)。
后面一问则有:
当问题规模为n时,时间复杂度Θ(n2)。
当x=16n时,时间复杂度Θ(x2)=Θ((16n)2)=Θ(256n2)。
转载请注明原文地址:https://tihaiku.com/congyezige/2409627.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在系统转换的过程中,旧系统和新系统并行工作一段时间,再由新系统代替旧系统的策略称
某项目包含的活动如下表所示,完成整个项目的最短时间为()周。不能通过缩短活动(
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
在下列调度算法中,()算法不会出现任务“饥饿”的情形。A.时间片轮转法 B.
下列叙述中正确的是()。A.算法的效率只与问题规模有关,与存储结构无关 B.
算法的时间复杂度取决于()。 A.问题的规模 B.问题的困难度 C.待处
MPEG视频中的时间冗余信息可以采用_()_的方法来进行压缩编码。A.帧间预测
中断响应时间是指()。A.从中断处理开始到中断处理结束所用的时间 B.从发出
中断响应时间是指_()_。A.从中断处理开始到中断处理结束所用的时间 B.从
随机试题
(94)Likefinefood,goodwritingissomethingweapproachwithpleasureand
Newevidenceofasick,deprivedpopulationworkingunderharshconditionsc
对审稿结论为“退修”的稿件,正确的处理方法有( )。A.修改后转其他出版社出版
以下关于下图所示有限自动机的叙述中,不正确的是()。 A.该自动机识别的
在项目实施过程中,( )容易增加冲突发生的概率.A.保证资源的供给 B.项目
下列哪种物质不属于纤维蛋白溶解系统A.纤溶酶原B.凝血酶原C.纤溶酶D.纤溶酶原
一住店客人未付房钱即想离开旅馆去车站。旅馆服务员揪住他不让走,并打报警电话。客人
在工程项目进度计划表示方法中,与横道图法相比,时标网络图的优点是能够()。
下列关于投标保证金的表述中,正确的是()。A.投标保证金一般不得低于投标报价的2
男性,18岁,乏力,纳差月余,病起发热3d后尿黄,巩膜、皮肤黄染,肝大肋下2cm
最新回复
(
0
)