【每日一练】时间复杂度&空间复杂度

1.下列叙述中正确的是
A)算法的时间复杂度与空间复杂度没有直接关系

B)一个算法的时间复杂度大，则其空间复杂度必定小

C)一个算法的空间复杂度大，则其时间复杂度也必定大

D)一个算法的空间复杂度大，则其时间复杂度必定小

答案：A

【解析】算法的复杂度主要包括时间复杂度与空间复杂度。算法的时间复杂度是指执行算法所需要的计算工作量，算法的空间复杂度是指执行这个算法所需要的内存空间。根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。

2.下列叙述中正确的是
A)算法的时间复杂度与空间复杂度一定相关

B)算法的效率只与问题的规模有关，而与数据的存储结构无关

C)算法的时间复杂度是指执行算法所需要的计算工作量

D)数据的逻辑结构与存储结构是一一对应的

答案：    C

【解析】算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关；算法的空间复杂度是指执行这个算法所需要的内存空间；根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关；数据的逻辑结构与存储位置无关，即与存储结构无关。

3.下列排序方法中，最坏情况下时间复杂度最小的是
A)直接插入排序

B)堆排序

C)冒泡排序

D)快速排序

答案：B

【解析】对长度为n的线性表排序，在最坏情况下，冒泡排序、快速排序和直接插入排序需要比较的次数为n(n－1)/2，而堆排序需要比较的次数为O(nlog2n)。

4.算法时间复杂度的度量方法是

A)执行算法所需要的时间

B)执行算法所需要的所有运算次数

C)算法程序的长度

D)执行算法所需要的基本运算次数

答案：D

【解析】算法的时间复杂度是指执行算法所需要的计算工作量，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

5.在最坏情况下
A)快速排序的时间复杂度比希尔排序的时间复杂度要小

B)快速排序的时间复杂度与希尔排序的时间复杂度是一样的

C)希尔排序的时间复杂度比直接插入排序的时间复杂度要小

D)快速排序的时间复杂度比冒泡排序的时间复杂度要小

上下滑动查看参考答案

答案：C

【解析】对长度为n的线性表排序，在最坏情况下，冒泡排序、快速排序和直接插入排序需要比较的次数为n(n－1)/2，希尔排序所需要的比较次数为O(n1.5)。

6.算法空间复杂度的度量方法是
A)执行算法所需要的存储空间

B)算法程序的长度

C)执行算法所需要的工作单元

D)算法所处理的数据量

答案：A

【解析】算法的空间复杂度是指执行这个算法所需要的内存空间。

7.下列叙述中错误的是
A)算法的时间复杂度与空间复杂度有直接关系

B)算法的空间复杂度与算法所处理数据的存储结构有直接关系

C)算法的时间复杂度与算法所处理数据的存储结构有直接关系

答案：A

【解析】 算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关；算法的空间复杂度是指执行这个算法所需要的内存空间；根据各自的定义可知，算法的时间复杂度与空间复杂度并不相关。

8.下列关于算法复杂度叙述正确的是
A)对同一个问题，采用不同的算法，则它们的时间复杂度是相同的

B)时间复杂度与采用的算法描述语言有关

C)时间复杂度与所用的计算工具无关

D)最坏情况下的时间复杂度一定高于平均情况的时间复杂度

答案：C