给定包含n 个正整数数组 A 和正整数 x，要判断数组 A 中是否存在两个元素之和等于 x，先用插入排序算法对数组 A 进行排序，再用以下过程 P 来判断是否存在两个元素之和等于 x。low=1;high=n;while（highlow） if A[low]+A[high]=x return true; ele if A[low]+A[high]x low++; ele high

2023-10-10 11:25分类：计算机类阅读：

给定包含n 个正整数数组 A 和正整数 x，要判断数组 A 中是否存在两个元素之和等于 x，先用插入排序算法对数组 A 进行排序，再用以下过程 P 来判断是否存在两个元素之和等于 x。low=1;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) 收起答案

答案： A

本题解析：

本题考查时间复杂度基本知识。第一空有一层循环while，遍历判断，所以时间复杂度为n；第二空如图所示：插入排序时间复杂为O(n2) ;