首页
登录
从业资格
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
admin
2022-08-02
57
问题
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个元素ai和aj,使得ai+aj=x。为了求解该问题,首先用归并排序算法对数组A进行从小到大排序;然后判断是否存在ai+aj=x,具体如下列伪代码所示,则求解该问题时排序算法应用了( )算法设计策略,整个算法的时间复杂度为( )i=1;j=nwhile i<jif ai+aj=x return trueelse if ai+aj>xj--;elsei++;return false;问题1选项A.分治B.贪心C.动态规划D.回溯问题2选项A.O(n)B.O(nlgn)C.O(n2)D.O(nlg2n)
选项
答案
AB
解析
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
本题从排序考虑,归并排序是根据分治法的算法策略。
对于时间复杂度,根据已有代码可以看到只有单层while循环,这段代码的时间复杂度为O(n),而整个算法分两个部分,排序部分和比较部分,对于排序部分,归并排序的时间复杂度为O(nlgn),T(n)=O(n)+O(nlgn),因此整个算法的时间复杂度为O(nlgn)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410309.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
信息资源规划可以概括为“建立两个模型和一套标准”,其中“两个模型”是指信息系统的
李某未经许可擅自复制并销售甲公司开发的财务管理软件光盘,已构成侵权。乙公司在不知
以下关于并发调度的说法中,正确的是()。A.以不同串行方式调度执行两个事务,
假设有两个数据库表isurance和employee分别记录了某地所有工作人员
假设某硬盘由5个盘片构成(共有8个记录面),盘面有效记录区域的外直径为30cm,
( )是构成我国保护计算机软件著作权的两个基本法律文件。单个自然人的软件著作权
将一个关系r分解成两个关系r1和r2,再将分解之后的两个关系r1和r2进行自然连
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以
假定用户A、B分别从I1、I2两个CA取得了各自的证书,下面( )是A、B互信
某系统由下图所示的冗余部件构成。若每个部件的千小时可靠度都为R,则该系统的千小时
随机试题
有关拖售权与随售权,下列表述正确的是( )。A.相比拖售权,随售权赋予股权基金
施工总承包管理模式与施工总承包模式在工作开展程序方面存在不同,具体体现在( )。
时间管理策略不包括A.学会拒绝 B.使用授权 C.善于使用助手 D.减少、
患者,女性,50岁。十二指肠溃疡病史10余年。近日患者自觉疼痛加剧,1小时前突感
个体身心发展包括_和_两方面的发展。() A.身体心理B.智力因素非
A、B两辆车同时从甲地出发前往乙地。两车距离乙地的路程y(千米)与行车时间x(小
根据GSP附录《温湿度自动监测》,药品都具有或多或少的温度敏感性,温度过高会导致
腹膜透析患者容易丢失的水溶性维生素是 (透析患者常用药物)A.乳果糖 B.铁
为维护自身合法权益,货物的收发货人可向代理其业务的代理报检单位索要检验检疫机构出
共用题干 2012年3月,某国有企业的会计工作发生以下情况:(1)厂长李某将朋
最新回复
(
0
)