判断题在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n ）。A 对B 错

题目

判断题

在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n ）。

对

错

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是()。

A.O(n)

B、O(n2)

C、O(nlog2n)

D、O(n3)

参考答案：B
解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。

第2题：

对n个元素进行快速排序时，最坏情况下的时间复杂度为(55)。

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

正确答案：D
解析：快速排序在最坏情况下的时间复杂度退化到一般的交换排序，即为O(n2)。

第3题：

以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。

A．快速排序算法是不稳定的排序算法

B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)

C．快速排序算法是一种分治算法

D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

正确答案：B
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：c_max=n(n-1)／2=O(²)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)

第4题：

时间复杂度不受数据初始状态影响而恒为0(nlog2n)的是( )。

A.堆排序
B.快速排序
C.希尔排序
D.冒泡排序

答案：A

解析：

堆排序无论是最好情况还是最坏情况，时间复杂度都是相等的。

第5题：

下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是

A、堆排序

B、起泡排序

C、直接选择排序

D、快速排序

正确答案：C

第6题：

对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是()

A. O(n)

B. O(n2)

C. O(nlog2n)

D. O(n3)

正确答案：B

第7题：

下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是(18)。

A．堆排序

B．冒泡排序

C．快速排序

D．SHELL排序

正确答案：A
解析：其他都不符合条件。

第8题：

在原始序列已经有序(升序或降序)的情况下，(60)算法的时间复杂度为O(n2)。

A．堆排序

B．插入排序

C．快速排序

D．归并排序

正确答案：C
解析：无论原始序列中的元素如何排列，归并排序和堆排序算法的时间复杂度都是 O(nlgn)。快速排序算法处理的最好情况指每次都是将待排序列划分为均匀的两部分，此时算法时间复杂度是O(nlgn)。在原始序列已经有序(升序或降序)的情况下，快速排序算法的时间复杂度反而为O(n²)。插入排序是将一个新元素插入已经排列好的序列中。如果在数据已经是升序的情况下，新元素只需插入到序列尾部，这就是插入排序的最好情况，此时计算时间为O(n)。

第9题：

对n个元素进行快速排序时，最坏情况下的时间复杂度为______。

A．O(log2n)

B．O(n)

C．O(nlog2n)

D．O(n2)

正确答案：D
解析：最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。其时间复杂度为0(n²)。

第10题：

下列排序算法中，时间复杂度不受数据初始状态影响恒为O(nlogn)的是()。

A.堆排序
B.冒泡排序
C.快速排序
D.直接插入排序

答案：A

解析：

堆排序和快速排序是O(nlogn)的复杂度，但是快速排序在数据初始状态有序的情况下蜕化为冒泡排序。

在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n ）。

题目

相似问题和答案

更多相关问题

相关内容