请注意，这道题中的所有快速排序题解的时间复杂度复杂度均是错误的

P1923 【深基9.例4】求第 k 小的数

Autre @ 2023-11-15 14:34:03

在每轮递归中，按照某种确定性方案选出一个元素作为基准元素，这样的算法的时间复杂度为 O(n^2)，只有随机选取一个元素才能让其复杂度降至期望 O(n\log n)，最劣 O(n^2)。

by Little_Cart @ 2023-11-15 14:57:39

@初星逝者不是？？？？你在干嘛？？？

ios+scanf ？？？？？

by Autre @ 2023-11-15 14:57:57

额，我这里说的“快速排序”题解，指的是手写的形如快速排序的二分查找算法

by ATZdhjeb @ 2023-11-15 14:58:13

@zhaohanwen 就是那个复杂度，说一直 O(nm) 是默认它会被卡。

现在几乎所有能卡 SPFA 的题都会卡

by No21 @ 2023-11-15 14:58:27

@初星逝者常数区别，但是 sort 将两者结合保证了 o(nlogn) 的复杂度

by Little_Cart @ 2023-11-15 14:58:30

@zhaohanwen 查到的没问题，但是大多数题目会把 SPFA 卡到最劣（）

by zhaohanwen @ 2023-11-15 14:59:04

@ATZdhjeb ~~所以SPFA死了对吧~~。

by No21 @ 2023-11-15 14:59:12

可是这个题和 spfa 有什么关系？？？

by Autre @ 2023-11-15 14:59:12

@zhaohanwen 你的意思可能是 SPFA 在随机数据下时间复杂度近似为 O(kn)，而非期望 O(kn)，只有随机化算法才有“期望时间复杂度”这种说法

by zhaohanwen @ 2023-11-15 14:59:36

@Castilian 确实。

by Little_Cart @ 2023-11-15 14:59:39

@No21 我不到啊