首页
登录
从业资格
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
admin
2022-08-02
51
问题
给定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,则该系统的千小时
随机试题
[originaltext]Announcer:Helloandwelcometotoday’sshow,Linda’sGarden.T
保险与彩票的共同点包括()。A.都是保障纯粹风险 B.都是互助机制 C.
通行地沟内的管道保温层外表至沟壁的距离大于或等于200mm,至沟顶的距离大于或等
猛性龋是() A.短期内多数或全口牙发生急性龋 B.龋坏包括牙面
在下列贵州的矿产资源中,位居全国前10位的是()。A.磷 B.铝土矿 C.锡
安宫牛黄丸中的君药是A.牛黄、麝香B.犀角、麝香C.朱砂、犀角D.牛黄、犀角E.
黄某于2006年11月突发精神病,患病期间独自订立一份遗嘱。经治疗,黄某病情好转
影响老年人的情绪和情感的是()。A.抑郁症 B.痴呆症 C.自闭症
实脾散中配伍木瓜的主要用意是( )。A.育阴护津 B.醒脾化湿 C.化湿和
男,48岁,糖尿病12年,每日皮下注射预混胰岛素治疗,早餐前30单位,晚餐前24
最新回复
(
0
)