首页
登录
从业资格
在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
在某个算法时间复杂度递归式T(n)=T(n-1)+n,其中n为问题的规模,则该算
考试题库
2022-08-02
56
问题
在某个算法时间复杂度递归式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.从
随机试题
[originaltext]Manystudentstrytostudythewholenightanddonotsleepbe
小学美术《变形的魅力》 一、考题回顾 题目来源1月5日下午陕西省渭南市面试考
飞达公司是一家汽车生产经营企业,经过多年的建设与发展,在汽车、摩托车、汽车发动机
爆炸性粉尘环境危险区域,在正常运行时,不可能出现爆炸性粉尘混合物的环境,即使出现
A.小讲课 B.头脑风暴法 C.小组讨论 D.案例分析 E.角色扮演培训
A.尿三氯化铁试验 B.尿嘌呤分析 C.染色体分析 D.血清铜蓝蛋白测定
治疗热闭神昏,常与麝香配伍相须使用的药物是()A.苏合香 B.石膏 C
蛔虫感染宜选用A.氯硝柳胺 B.哌嗪 C.阿苯达唑 D.噻嘧啶 E.甲苯
(2017年真题)变压器室外安装时,安装在室外部分的有()。A.电压互感器 B
绝热层施工技术要求,正确的是()。A.当采用一种绝热制品,保冷层厚度为90m
最新回复
(
0
)