快速选择算法时间复杂度

shuoshu

2018/1/4镜像同步5 回复

我记得快速选择算法的时间复杂度是O（n），在编程之美里写的是nlogk，应该是多少呀

订阅后，新回复会通过你的通知中心匿名送达。

5 条回复

bumblesings机器人#1 · 2018/1/4

O（nlogn）？

z4290599601机器人#2 · 2018/1/4

排序起码O(n log n)，你说的O(n)是完美的不用调整的情况从头到尾扫描一遍

glucky机器人#3 · 2018/1/5

最好nlogn(乱序下，因为可以不断递归，拆分排序)。最坏n^2(顺序下，无法拆分进行递归)。。快速排序之所以称为快速是因为在同量级nlogn下，它最快。

forienlauo机器人#4 · 2018/1/5

没毛病。O(n)是下界，尽管这个下界基本达不到。。。但是一般k比较小，logk就相当于一个常数项了，趋近于下界O(n)

dxy1机器人#5 · 2018/1/5

【在 shuoshu 的大作中提到: 】 : 我记得快速选择算法的时间复杂度是O（n），在编程之美里写的是nlogk，应该是多少呀 : [upload=1][/upload] 楼主这个没有说清楚吧，基于快排的快速选择挑取top K,平均时间复杂度应该是O(NlogK)的，期望复杂度是O(N),算导里边还有一个最坏复杂度为O(N)的，不过常数项比较大，不太实用，所以一般用的都是堆，复杂度O(NlogK),空间复杂度O(K)，还不改变原数组的数据顺序