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

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

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

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

by 初星逝者 @ 2023-11-15 15:00:45

@Little_Cart 我看成这篇四年前的题解在现在过不去了，我的问题

by 初星逝者 @ 2023-11-15 15:01:37

@zhaohanwen 6

by Little_Cart @ 2023-11-15 15:01:39

@初星逝者不是，我的意思是你为什么要把 ios::sync_with_stdio(0); 和 scanf 混用啊哥

by 初星逝者 @ 2023-11-15 15:02:46

@Little_Cart 没有没有，一时疏忽，感谢提醒

by NightmareAlita @ 2023-11-15 15:07:23

@Castilian 泰剧辣！！！

by rome1 @ 2023-12-14 21:05:57

@Castilian 那为什么这些题解能A啊可以给一组这些题解会TLE的数据吗

上一页 |