n log n
by zyxawa @ 2024-02-26 15:35:26
$O(n\log n)$
吧……
by Locix_Elaina_Celome @ 2024-02-26 15:35:50
n sqrt n
by jijidawang @ 2024-02-26 15:37:19
设 $h_i$ 为节点 $i$ 的期望高度，$s_i$ 为大小为 $i$ 的期望深度之和，令 $h_1 = 1$。
有
$$
h_i = \dfrac{\sum_{j = 1}^{i-1}h_j}{i-1}+1 = \dfrac{s_{i-1}}{i-1}+1\\
s_i = s_{i-1} + h_i = \dfrac{i}{i-1}s_{i-1} + 1
$$
展开之后就是 $s_i = \sum_{j=1}^i \dfrac ij$，就是调和级数吧。
by Ew_Cors @ 2024-02-26 15:38:15
可能有问题，你先看看，，
by Ew_Cors @ 2024-02-26 15:38:36
看怎么随机
如果是每一个点随机父亲，那么应该是 $ O(n\log n) $。
如果是随机 Prufer 序列，那么应该是 $ O(n\sqrt{n}) $。
不保证正确（
by Wuyanru @ 2024-02-26 15:48:35
Orz 懂了，谢谢大牢们:)
by xcyyyyyy @ 2024-02-26 16:05:55
@[jijidawang](/user/227514) 哎，这个有相关的文献吗问问，刚刚上某度也没查到。这个根号的界咋证啊
by pp_orange @ 2024-02-26 16:13:00
@[pp_orange](/user/224443) idk
by jijidawang @ 2024-02-26 16:38:36