怎么缩短时间复杂度啊

KonjacTeng @ 2024-07-16 09:45:23

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k,num[5000000];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&num[i]);
    sort(num,num+n);
    printf("%d",&num[k]);
    return 0;
}

by xiao7_Mr_10_ @ 2024-07-16 09:50:50

@xinxin2022 线段树二分,可持久化线段树

by _Hzx_ @ 2024-07-16 09:51:23

@tengzichen 这题是练分治写归并排序的。

by _Hzx_ @ 2024-07-16 09:52:28

@xiao7_Mr10

@xiao7_Mr10 基准数归位后判断其位置，然后只递归一边，近似O(n)啊老底

自己对自己说话（）

快排就是会被卡成 \log。

by xinxin2022 @ 2024-07-16 09:53:31

@xiao7_Mr10 我可持久化自行车+拓扑排序

桶排是不是也行

by xinxin2022 @ 2024-07-16 09:54:30

@Hzx 甚至对超级毒瘤数据会退化到 n^2 级别

by _Hzx_ @ 2024-07-16 09:54:40

甚至可以堆排；可以用 set 排。 @tengzichen

by xiao7_Mr_10_ @ 2024-07-16 09:54:57

@Hzx ......不是，我们两不在一个频道上，我把代码写出来你看看就知道了

by xinxin2022 @ 2024-07-16 09:57:13

@xiao7_Mr10 您是手写随机基准数吗？

深基上好像讲过如何卡这题

by _Hzx_ @ 2024-07-16 09:57:20

@xinxin2022 确实，但那种数据很难造。

@xiao7_Mr10 是不是就你学过快排啊。说了快排不具有稳定性，很容易就被卡成 O(n \log n)，O(n) 只是期望复杂度，甚至有一点点可能会被卡到 O(n^2)。

by _Hzx_ @ 2024-07-16 09:58:35

@xiao7_Mr10 真是巨佬，我所知道的桶排是 O(n)，但如果数据打了写不了，用 hash 可能复杂度会增加。