n sqrt n
by liqingyang @ 2023-03-19 13:35:16
@[lovely_seele](/user/714821) n 根号 n 啊。
by hanjinghao @ 2023-03-19 13:37:20
莫队的随机数据期望复杂度就是根号吧。
by E1_de5truct0r @ 2023-03-19 13:39:11
啊，随机不会改变复杂度的级别吗。
by loser_seele @ 2023-03-19 13:39:35
@[lovely_seele](/user/714821) 莫队复杂度平均 n 根号 n、最坏 n 根号 n、最好 O(n)
by hanjinghao @ 2023-03-19 13:42:01
@[lovely_seele](/user/714821) 除非随出来的数据里，左右端点很集中，不然应该就是根号的。
by E1_de5truct0r @ 2023-03-19 13:44:13
@[lovely_seele](/user/714821) 随机了每个左端点的块内的期望还是 $O(\sqrt n)$，右端点在同一块内的分布还是 $O(n)$。
by Usada_Pekora @ 2023-03-19 13:45:14
感谢，本帖结。
by loser_seele @ 2023-03-19 13:45:27