首页
登录
从业资格
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个
admin
2022-08-02
72
问题
给定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,则该系统的千小时
随机试题
Smokingis______inpublicbuildings.A、avoidedB、prohibitedC、rejectedD、repell
A--TajMahalB--HangingGardensofBabylonC
A.informedB.careerC.presentingD.relevant
【S1】[br]【S5】H此处需要一个形容词,在所剩下的三个形容词里,只有next符合题意。
肾脏移植前输血可导致移植肾存活几室( )。A.加大 B.减小 C.为0
关于中药使用说法错误的是A:质地较轻或成分容易煎出的药物如花、叶、草之类,用量不
电子商务对生产经营的影响有()A.降低交易成本 B.增加企业交易机会 C.延
某耐火等级为一级的高层住宅建筑,下列关于其井道的防火要求,不正确的是()。A.
房地产市场状况分析,是介于宏观和微观的分析,市场状况分析一般包括()A:供给分析
采用定额单价法编制施工图预算的主要步骤包括:①准备材料并熟悉施工图纸,②编制工料
最新回复
(
0
)