快速排序的复杂度不是应该跟初始化序列是否有序没有关系吗?关键看那个一分为2的标准的选取。即使初始有序,用随机选取的方式,怎么回成了O(n^2)呢,如果恰恰每次选的都是中间大小的,效果不是最好吗。即使是初始序列完全无须,老选到最大或者最小的,效果不是也是很差吗?怎么到处都在说初始有序的情况下快排的时间复杂度为O(n^2),求大神解释
2条回答 默认 最新
- Valtava 2016-07-15 15:43关注
快排复杂度和序列是否有序是有关系的,除非每次选取基准元素时你都选取中间那个(比如使用std::nth_element)
怎么到处都在说初始有序的情况下快排的时间复杂度为O(n^2)
常见的教材,一般选择数组的最后一个元素(也有选择第一个元素的)作为pivot,以此为基准将数组分为两部分,那么很显然,当数组有序的时候,
每次递归只是将一个含有n个元素的数组分成了一个只包含1个元素的数组和一个包含n-1个元素的数组,因此需要进行n次分组,而每次分组都要遍历数组(n次比较)以将其分成两部分,
因此这种情况下复杂度为O(n^2)。 因此对于快排,最好的情况也要nlog(n),最坏则需要n^2,也即:很多时候快排并不快解决 无用评论 打赏 举报