对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是__。

admin2014-12-25 60

问题对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。

选项

答案O(nlog₂n) O(n²)

解析快速排序的基本思想是由选取的中间元素把整个待排序空间分成左、右两个区域，其中左边区域中元素的关键字都不大于中间元素的关键字，而右边区域中元素的关键字都不小于中间元素的关键字，接下来再按上述思路继续对各个区域进行划分。最好情况下，每次选定的中间元素正好将待排序空间分成几乎等长的两个区域，这样仅需log₂n趟划分即可。每趟划分所需时间复杂度为O(n)，最好情况下的时间复杂度是O(nlog₂n)。
最坏情况下，每次选取的中间元素不是最大就是最小，因此划分出的两个区域一个为空，而另一个仅比原空间少一个元素，故需要n一1趟划分。每趟划分的时间复杂度为O(n)，因此，最坏情况下的时间复杂度为O(n²)。

转载请注明原文地址:https://www.kaotiyun.com/show/2iVx777K

本试题收录于：数据结构导论题库理工类分类

数据结构导论

理工类

相关试题推荐

随机试题

最新回复(0)

对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是__。

数据结构导论

理工类

传递函数的量纲是根据________来决定的。

一系统在扰动作用下的误差函数为EN(s)=，则系统由扰动引起的稳态误差essN等于【】

在时域中用线性常微分方程描述系统的动态特性；在复数域或频域中，用________来描述系统的动态特性。

采用非屏蔽双绞线UTP将站点连接到集线器上，一段双绞线的最大长度为【】

______是由Cisco公司专门为小型和中型网络开发的一套基于PC的集成式网络配置和诊断工具。

下列软件中，不是基于P2P模式的是【】

细缆以太网的最大网络干线长度为【】

数据存储条目主要描写该数据存储的_及有关的数据流、____要求。

甘特图是一个二维平面图，其中横向维表示__或活动的时间，纵向维表示工作的_。

设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“_______”。

关于一级注册建造师执业区域范围说法正确的是()。

在缺氧条件下，丙酮酸还原为乳酸的意义是使NAD+再生。()

最可能的诊断为确诊后，应采取的治疗措施中最重要的是

消心痛的禁忌症有

一刚性容器被绝热材料所包裹。容器内有一隔板将容器分成两部分，一部分有气体，另一部分为真空。假设气体为理想气体，若轻轻将隔板抽开，此容器内气体的内能△E()。

承兑人在异地的，贴现的期限应另加()天的划款日期。

进口货物分设特惠税率、协定税率、最惠国税率、普通税率、暂定税率等。其中最惠国税率是最低的税率。()

信用风险管理不应当仅仅停留在单笔贷款的层面上，还应当从贷款组合的层面进行()。

简述语文教学目标确立的原则。

在Cache块替换算法中，下述说法错误的是

对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。

数据结构导论

理工类

传递函数的量纲是根据________来决定的。

一系统在扰动作用下的误差函数为EN(s)=，则系统由扰动引起的稳态误差essN等于【】

在时域中用线性常微分方程描述系统的动态特性；在复数域或频域中，用________来描述系统的动态特性。

采用非屏蔽双绞线UTP将站点连接到集线器上，一段双绞线的最大长度为【】

______是由Cisco公司专门为小型和中型网络开发的一套基于PC的集成式网络配置和诊断工具。

下列软件中，不是基于P2P模式的是【】

细缆以太网的最大网络干线长度为【】

数据存储条目主要描写该数据存储的_____及有关的数据流、________要求。

甘特图是一个二维平面图，其中横向维表示________或活动的时间，纵向维表示工作的_______。

设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“_______”。

关于一级注册建造师执业区域范围说法正确的是()。

在缺氧条件下，丙酮酸还原为乳酸的意义是使NAD+再生。()

最可能的诊断为确诊后，应采取的治疗措施中最重要的是

消心痛的禁忌症有

一刚性容器被绝热材料所包裹。容器内有一隔板将容器分成两部分，一部分有气体，另一部分为真空。假设气体为理想气体，若轻轻将隔板抽开，此容器内气体的内能△E()。

承兑人在异地的，贴现的期限应另加()天的划款日期。

进口货物分设特惠税率、协定税率、最惠国税率、普通税率、暂定税率等。其中最惠国税率是最低的税率。()

信用风险管理不应当仅仅停留在单笔贷款的层面上，还应当从贷款组合的层面进行()。

简述语文教学目标确立的原则。

在Cache块替换算法中，下述说法错误的是

对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是__。

数据存储条目主要描写该数据存储的_及有关的数据流、____要求。

甘特图是一个二维平面图，其中横向维表示__或活动的时间，纵向维表示工作的_。