奇怪的想法：猴子排序

Iniaugoty @ 2023-03-01 13:39:34

void sort(int &A[]){
    if(A为空) return;
    找到上升子序列B;
    将这个子序列之外的存入A;
    打乱A;
    sort(A);
    归并A B;
}

by fjy666 @ 2023-03-01 13:40:14

O(非常差)

by AC_CSP @ 2023-03-01 13:41:47

找到上升子序列B;

这一步具体怎么实现的呢

by rainygame @ 2023-03-01 13:42:05

@gty314159 大概是 O(n \log^2 n) 吧。

by DeletedUser @ 2023-03-01 13:42:27

O(1) or O(1145141919810)

看你自己的人品

by QwQcOrZ @ 2023-03-01 13:46:40

by Imiya @ 2023-03-01 13:49:43

借楼问一下一个随机序列的最长不降子序列期望长度

by _HL_ @ 2023-03-01 13:50:15

如果每次找B找到lis是不是应该挺快的啊 T(n)=T(n-\sqrt n)+n

by myee @ 2023-03-01 13:50:30

查了一下，排列的最长上升子序列长度是期望 O(\sqrt n) 的？

by _HL_ @ 2023-03-01 13:51:03

@yuanjiabao lis应该是根号的

by myee @ 2023-03-01 13:51:11

单轮咋 O(n) 找 LIS 啊。