【单选题】下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法:针对一个“学生”数据表,如下示意,找出“成绩”为某一分数的所有学生。 关于三个算法的复杂性,下列说法正确的是_____。
A. 算法A1、A2和A3的时间复杂性都为O(n) B. 算法A1和A2的时间复杂性为O(1)，算法A3的时间复杂性为O(n) C. 算法A1的时间复杂性为O(n)，算法A2的时间复杂性为O(n/2)，算法A3的时间复杂性为O(n/4) D. 算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为O(nlogn)
A. 算法A1、A2和A3的时间复杂性都为O(n) B. 算法A1和A2的时间复杂性为O(1)，算法A3的时间复杂性为O(n) C. 算法A1的时间复杂性为O(n)，算法A2的时间复杂性为O(n/2)，算法A3的时间复杂性为O(n/4) D. 算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为O(nlogn)
举一反三
- 查看本试题中关于回文判断的算法题目，分析算法的时间复杂性，如下描述中正确的是哪个？ A: 该算法时间复杂性的递归定义为： T(n)=T(n-1)+1，if n>1;T(n)=O(1),if n≤1。T(n)=O(n), T(n)=Ω(1) B: 该算法时间复杂性的递归定义为： T(n)=T(n-1)+1,ifn>1;T(n)=O(1),if n≤1。T(n)=O(n), T(n)=Ω(n) C: 该算法时间复杂性的递归定义为： T(n)=T(n-2)+1，if n>1;T(n)=O(1), if n≤1。T(n)=O(n), T(n)=Ω(1) D: 该算法时间复杂性的递归定义为： T(n)=T(n-2)+1，if n>1;T(n)=O(1), if n≤1。T(n)=O(n), T(n)=Ω(n)
- 对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（） A: O（n） B: O（n） C: O（1） D: O（logn）
- 对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。 A: O(n) B: O(n2) C: O(1) D: O(log2n)
- 问题的计算时间下界为Ω(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。
- 对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。 A: O( B: O(n2) C: O(1) D: O(log2