首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设某算法的计算时间可用递推关系式T(n)=2T(n/2)n表示,则该算法的时间复杂度为( )。
设某算法的计算时间可用递推关系式T(n)=2T(n/2)n表示,则该算法的时间复杂度为( )。
admin
2019-06-12
38
问题
设某算法的计算时间可用递推关系式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
软件设计师上午基础知识考试
软考中级
相关试题推荐
物理层信号的功能特性__________。
下列关于软件著作权中翻译权的叙述不正确的是:翻译权是指______的权利。
以下关于三重DES加密的叙述中,正确的是(41)________________。
DNS正向搜索区的功能是将域名解析为IP地址,WindowsXP系统中用于测试该功能的命令是____________。
假设网络的生产管理系统采用B/S工作方式,经常上网的用户数为100个,每个用户每分钟平均产生11个事务,平均事务量大小为0.06MB,则这个系统需要的信息传输速率为(34)。
在以太网协议中使用1-坚持型监听算法的特点是(62)。
关于原型化开发方法的叙述中,不正确的是(6)。
以下关于Cache的叙述中,正确的是()。
请补充函数fun(),该函数的功能是将字符串tt中的大写字母都改为对应的小写字母,其他字符不变。例如,若输入“AreyoucomefromSichuan?”,则输入“areyoucomefromsi-chuan?”。注意:部分源程
随机试题
政治发展的变化主要表现在两个方面,一是在特定社会历史阶段的量变过程,二是()。
抽样方法按照是否遵循随机原则可分为()
A.24小时动态心电图检查B.201Ti或99Te—MIBI核素心肌显像C.肺通气灌注扫描D.胸部X线片E.心脏MRI患者反复发作性心悸、胸闷伴黑噱,为明确病因,应首选的检查是
A.阴离子B.阳离子C.两性离子D.两者均是E.两者均不是下列表面活性剂起表面活性的部分含有上述哪种离子
西方巴洛克风格室内装饰装修的特点有()。
据统计,2011年我国国内生产总值为74970亿美元;2011年我国货物服务出口总额为20867亿美元,经常账户收支顺差2017亿美元,资本和金融账户收支顺差2211亿美元,国际储备资产增加3878亿美元;2011年年底未清偿外债余额5489亿
甲公司业务经理乙长期在丙餐厅签单招待客户,餐费由公司按月结清,后乙因故辞职,月底餐厅去结账时,甲公司认为,乙当月的几次用餐都是招待私人朋友因而拒付乙所签单的餐费,下列中哪一选项是正确的?()
ANEWCRUISESHIPOneofthebiggestpassengershipsinhistory,theIslandPrincess,carriespeopleoncruisesaroundtheCa
The______newsisthatemploymentratesinourcountryaresignificantlyontherise.
TheNewZealandStormPetrelwasabirdlongthought(i)______,butin2003severalbirdswerespottedforthefirsttimein150
最新回复
(
0
)