如何使std::sort从nlogn变成n^2？

RT
最简单的栗子就行了

tarjin (ldq101) LV 4 @ 2021-03-11 18:41:06

sort的底层很复杂有很多种排序方式综合使用，其中最主要的是快速排序，对于快速排序原本序列有序可以卡到O(n^2)但如果随机取pilot就很难被卡掉了。
吴振宇 (老黑) LV 8 @ 2021-03-10 22:27:20

原本的序列已经有序
Mooos_MoSheng LV 4 @ 2021-03-09 14:51:17

似乎是做不到的。
因为std::sort在快排的基础上配合插入排序使时间复杂度更优，几乎不可能卡到n^2。
ttcwws LV 0 @ 2021-02-20 12:39:06

不会的，它最坏O(nlogn)

4 条评论