给定n个整数构成的数组A={a1,a2,……,an}和整数x,判断A中是否存在两个元素ai和aj,使的ai+aj=x。为了求解问题,首先用归并排序算法对数组A进行从大到小排序;然后判断是否存在ai+aj=x,具体的方法如下列伪代码所示。则求解该问题时排序算

admin2019-07-12  27

问题 给定n个整数构成的数组A={a1,a2,……,an}和整数x,判断A中是否存在两个元素ai和aj,使的ai+aj=x。为了求解问题,首先用归并排序算法对数组A进行从大到小排序;然后判断是否存在ai+aj=x,具体的方法如下列伪代码所示。则求解该问题时排序算法应用了(62)算法设计策略,整个算法的时间复杂度为(63)。
i=1;j=n
WhileiIfrdi+ai=xretumtree
Els
(63)

选项 A、O(n)
B、0(nlgn)
C、O(n2)
D、O(nlg2n)

答案B

解析 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。分支算法的时间复杂度为O(nlgn)。
转载请注明原文地址:https://kaotiyun.com/show/E6CZ777K
0

最新回复(0)