首页
登录
从业资格
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
admin
2022-08-02
50
问题
给定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,则该系统的千小时
随机试题
Sixtydayswalkingovericeandsnowintemperatureaslowas-45°C,withn
对消防用水水质的要求,以下哪条错误?( )A.无特殊要求 B.水中杂质悬浮物
将一个递归算法改为对应的非递归算法时,通常需要使用()。A.优先队列 B.队
下面是两个关于教学目标设计的案例: 【案例1】消费者的合法权益受法律保护 教
流行性出血热的病原体属于A.细菌 B.立克次氏体 C.病毒 D.螺旋体
红外测温对待测设备应处于()状态。(A)热备用(B)冷备用(C)
()kV变电站内的110kV母线保护宜按双套配置。(A)110(B)220
某施工队计划用120个劳动力在规定时间内完成一定的挖土任务,施工25天后,因调走
下列关于金融期货交易结算制度的表述中,错误的是()。A.全面结算会员期货公司应
下列癌症中,最常引起血道转移的是( )。A.甲状腺乳头状癌 B.子宫绒毛膜癌
最新回复
(
0
)