2. 计算机
  3. 给定包含n个正整数的数组A和正整数x，要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。 low=l； high=n； while(high＞low) if A[low]+A[hig

给定包含n个正整数的数组A和正整数x，要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。 low=l； high=n； while(high＞low) if A[low]+A[hig

admin2019-02-25  106
问题 给定包含n个正整数的数组A和正整数x，要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。
low=l；
high=n；
while(high＞low)
if A[low]+A[high] =x return true；
else  if A[low]+A[high]  ＞ x low++；
else high--；
return  false；
则过程P的时间复杂度为  ①  ，整个算法的时间复杂度为  ②  。
②处应填入？
选项 A、O(n)
B、O(nlgn)
C、O(n2)
D、O(n2lgn)
答案C
解析 本题考查算法分析技术，要求考生掌握基本的算法设计和分析知识。
由伪代码分析过程P的时间复杂度，该过程涉及一重循环，时间复杂度为n。整个算法包括两个步骤，先对数组A排序，题干已经明确指出用插入排序算法排序，因此时间复杂度为O(n2)，然后再用过程P判断，该步骤时间复杂度为O(n)，总的时间复杂度为O(n2)。
转载请注明原文地址:https://kaotiyun.com/show/w1PZ777K
本试题收录于： 软件评测师上午基础知识考试题库软考中级分类
0

软件评测师上午基础知识考试

软考中级

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