(2013年上半年上午试题62、63)给定n个整数构成的数组A={a1，a2，……，an}和整数x，判断A中是否存在两个元素ai和aj，使得ai+aj=x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在ai+aj=x，具体的方法

admin2021-01-13 1.8K+

问题 (2013年上半年上午试题62、63)给定n个整数构成的数组A={a₁，a₂，……，a_n}和整数x，判断A中是否存在两个元素a_i和a_j，使得a_i+a_j=x。为了求解问题，首先用归并排序算法对数组A进行从大到小排序；然后判断是否存在a_i+a_j=x，具体的方法如下列伪代码所示。则求解该问题时排序算法应用了________(62)算法设计策略，整个算法的时间复杂度为_____(63)。
i=1；j=n
while i＜j
If a_i+a_j=x return true
Else if a_i+a_j＞x
J--；
Else
I++；
Return false；
(63)

选项 A、O(n)
B、O(nlgn)
C、O(n²)
D、O(nlg²n)