首页
登录
从业资格
某算法的时间复杂度可用递归式表示,若用表示该算法的渐进时间复杂度的紧致界,则正确
某算法的时间复杂度可用递归式表示,若用表示该算法的渐进时间复杂度的紧致界,则正确
题库
2022-08-02
42
问题
某算法的时间复杂度可用递归式
表示,若用表示该算法的渐进时间复杂度的紧致界,则正确的是( )。
选项
答案
A
解析
在本题中,我们关键要理解算法的渐进紧致界的概念,举个例子来说吧,假设当N>N0时,函数f(N)在一个常数因子范围内等于g(N),则称g(n)是f(n)的一个渐近紧致界。
【《软件设计师教程(第5版)》--P422页】
根据主定理(定理8.1),此递归式中,a=2,b=2,logba=1,则f(n)=nlgn=nlogbalgkn=nlogbalgn,属于规则(2),(其中k=1),因此,T(n)=O(nlogbalgk+1n)=O(nlg2n)。本题选择A选项。
本题中给出的递归式的渐进紧致界应该是A。
转载请注明原文地址:https://tihaiku.com/congyezige/2409918.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
根据历史数据,确定一个就诊人员是否可能患心脏病,可以采用( )算法。A.C4.
关于聚类算法K-Means和DBSCAN的叙述中,不正确的是( )。A.K-M
进程P1、P2、P3、P4和P5的前趋图如下所示: 若用PV操作控制进程P
某企业部门关系模式Dept(部门号,部门名,负责人工号,任职时间),员工关系模式
某项目包含的活动如下表所示,完成整个项目的最短时间为( )周。不能通过缩短活动
以下加密算法中适合对大量的明文消息进行加密传输的是( )A.RSA B.SH
地址编号从80000H到BFFFFH且按字节编址的内存容量为( )KB,若用1
假设某分时系统采用简单时间片轮转法,当系统中的用户数为n、时间片为q时,系统对每
一条指令的执行过程可以分解为取指、分析和执行三步,在取指时间t取指=3△t、分析
从时间、地区和商品种类三个维度来分析某电器商品销售数据属于()。A.ETL
随机试题
A—collectiveactionI—psychologicalsupportB—competitoranalysisJ—performanc
WhowillreplaceJaneJohnsontocontacttheircustomers?___________________.Jo
PartⅡReadingComprehension(SkimmingandScanning)Directions:Inthispart,y
[originaltext]Sir,wouldyoulikeaglassofwine?[/originaltext][audioFiles]2
免疫系统的三大功能是________、_______和__________。
A.胶乳凝集抑制试验B.单克隆抗体胶体金试验C.ELISAD.放射免疫试验E.电
某男,35岁,农民。诉头晕、耳鸣、心悸、气急近1个月。一般检查:体温正常,脉搏9
氟喹诺酮类药物抑制下列何种酶而抗菌A.二氢叶酸合成酶 B.转肽酶 C.DNA
雷诺综合征好发于 A.青壮年男性B.青壮年女性C.老年男性D.老年女性
“备注”项( )A.A:XXXXXXXX B.O:XX
最新回复
(
0
)