2. 从业资格
  3. 给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个

给定n个整数构成的数组A={a1,a2,…,an}和整数x,判断A中是否存在两个

admin2022-08-02  14
问题 给定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://www.tihaiku.com/congyezige/2410309.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)