首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设某算法的计算时间可用递推关系式T(n)=2T(n/2)n表示,则该算法的时间复杂度为( )。
设某算法的计算时间可用递推关系式T(n)=2T(n/2)n表示,则该算法的时间复杂度为( )。
admin
2019-06-12
37
问题
设某算法的计算时间可用递推关系式T(n)=2T(n/2)n表示,则该算法的时间复杂度为( )。
选项
A、O(lgn)
B、O(nlgn)
C、O(n)
D、O(n
2
)
答案
B
解析
递推关系式T(n)=2T(n/2)n其实是在给n个元素进行快速排序时最好情况(每次分割都恰好将记录分为两个长度相等的子序列)下的时间递推关系式,其中T(n/2)是一个子表需要的处理时间,n为当次分割需要的时间。注意,这里实际上是用比较次数来度
量时间。可以对此表达式进行变形得
用n/2代替上式中的n可得
继续用n/2代替上式中的n可得
算法共需要进行[1bn]+1次分割(n个元素的序列的对半分割树的高度跟具有n个结点的完全二叉树高度相等,软设级别的只需知道即可,不必深究),将上述[1bn]+1个式子相加,删除相互抵消的部分得
而T(1)=1,那么上式可转化为
T(n)=n[1bn]+2n
而在求时间复杂度时关注“大头”,注意到O(n)
T(n)=O(nlogn)=O(nlgn)
数学上,一般将底为10的对数简略写成lgn。
转载请注明原文地址:https://kaotiyun.com/show/0ECZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网的最大帧长为1518字节,每个数据帧前面有8个字节的前导字段,帧间隔为9.6μs,对于10BASE-5网络来说,发送这样的帧需要多少时间?(64)
下面的光纤以太网标准中,支持1000m以上传输距离的是____________。
假设网络的生产管理系统采用B/S工作方式,经常上网的用户数为100个,每个用户每分钟平均产生11个事务,平均事务量大小为0.06MB,则这个系统需要的信息传输速率为(34)。
若一个项目由9个主要任务构成,其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数,该项目的关键路径是(1),完成项目所需的最短时间是(2)天。(1)
SHA-1是一种将不同长度的输入信息转换成__________位固定长度摘要的算法。
某网络工程计划图如下所示,边上的标记为任务编码及其需要的完成时间(天),则整个工程的工期为(10)。
SDES是一种____________算法。
以下关于在IPv6中任意播地址的叙述中,错误的是_____________。
阅读下列Java程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】StringEditor类的功能是:已知一个字符串,返回将字符串中的非字母字符都删除后的字符串。public(1){publicstati
随机试题
双侧游离端缺失属于Kennedy分类的
超声检查在口腔颌面部不适用于
人体实验应遵循的伦理原则包括,除外A.知情同意的原则B.维护受试者利益的原则C.科学的原则D.医学发展和人类健康利益第一的原则E.有利于维护和促进人类健康的原则
在一起行政诉讼案件中,被告进行处罚的依据是国务院某部制定的一个行政规章,原告认为该规章违反了有关法律。根据我国宪法规定,下列哪一机关有权改变或者撤销不适当的规章?
容量为100MW的机组,采用发电机一三绕组变压器单元接线时宜符合下列何项的要求?
通常情况下,合同双方通过设定(),来克服成本加酬金合同的缺点。
以公司的内部管辖关系为标准,可以将公司分为母公司和子公司。()
根据利率平价学说,利率相对较高的国家未来货币升水的可能性大。
设n阶方阵A的各行元素之和均为零,且RA=n—1,则线性方程组Ax=0的通解为__________。
以下选项中,不能对主函数中变量i和j的值进行交换的程序是()。
最新回复
(
0
)