国家电网招聘
最好情况下的算法时间复杂度为O(n)的是()。A.插入排序 B.归并排序 C.快速排序 D.堆排序
题目
B.归并排序
C.快速排序
D.堆排序
相似问题和答案
第1题：
下列排序方法中，最好情况下，时间复杂度为O(n)的算法是______。
A．选择排序
B．归并排序
C．快速排序
D．直接插入排序
解析：各种排序算法性能比较如下：
第2题：
A.O(n)
B、O(n2)
C、O(nlog2n)
D、O(n3)
解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。
第3题：
在其最好情况下的算法时间复杂度为O(n)。
A．插入排序
B．归并排序
C．快速排序
D．堆排序
解析：本题考查的是排序算法的时间复杂度。无论原始序列中的元素如何排列，归并排序和堆排序算法的时间复杂度都是 O(nlgn)。快速排序算法处理的最好情况指每次都是将待排序列划分为均匀的两部分，此时算法时间复杂度是O(nlgn)，在原始序列已经有序(升序或降序)的情况下，快速排序的时间复杂度反而为O(n2)。而插入排序是将一个新元素插入已经排列好的序列中，显然，在输入数据已经是升序的情况下，新元素只需插入到序列尾部，这就是插入排序的最好情况，此时计算时间为O(n)。
第4题：
若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。
A．O(n2)
B．O(n)
C．O(logn)
D．O(nlogn)
解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和 f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、 O(logn)和O(nlogn)中，复杂度最小的是O(logn)。
第5题：
A、O(logn)
B、O(n)
C、O(n*logn)
D、O(n2)
第6题：
希尔排序算法的时间复杂度为O(n2)。()
第7题：
A对于任何的数据量，A算法的时间开销都比B算法小
B随着问题规模n的增大，A算法比B算法有效
C随着问题规模n的增大，B算法比A算法有效
D对于任何数据量，B算法的时间开销都比A算法小
第8题：
关于排序算法的以下说法，错误的是()
A.归并排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
B.堆排序平均时间复杂度O(nlogn)，最坏时间复杂度O(nlogn)
C.冒泡排序平均时间复杂度O(n^2)，最坏时间复杂度O(n^2)
D.快速排序的平均时间复杂度O(nlogn)，最坏时间复杂度O(n^2)
第9题：
n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为______。
A．O(1)
B．O(1og2n)
C．O(n2)
D．O(n)
解析：最好情况下至少需要一趟排序，即比较n-1次。选项D为本题正确答案。
第10题：
直接选择排序的平均时间复杂度为(17)。最好情况下时间复杂度为O(n)的排序算法是(18)。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(19)。
A．O(n)
B．O(nlogn)
C．O(n2)
D．O(logn)