@[zero4338](/user/174469) 其实是 $O(n)$ 的 但是很难卡
by Rui_R @ 2021-04-18 21:00:29
@[Rui_R](/user/101984) 这个能证明吗
by zero4338 @ 2021-04-18 21:26:45
@[zero4338](/user/174469) 呃，意思是单次最坏 $O(n)$
by Rui_R @ 2021-04-19 07:46:54
@[Rui_R](/user/101984) 那随机数据下均摊复杂度是多少
by zero4338 @ 2021-04-19 07:56:01
@[zero4338](/user/174469) 这个我也不清楚，抱歉
（但是不去专门卡的话跑得飞快）
by Rui_R @ 2021-04-19 07:58:24
@[Rui_R](/user/101984) 好吧 谢谢 qwq
by zero4338 @ 2021-04-19 08:03:28
@[zero4338](/user/174469)
K-D tree 随机数据下均摊复杂度应该是 $O(n^{\frac{k-1}{k}})$ 的，其中 $k$ 为维数。
但其实单次查询最坏能被卡成 $O(n)$，您应该做过 P4169，[这里](https://www.luogu.com.cn/problem/U25704)有能把 K-D tree 卡成 $O(n^2)$ 的 hack 数据，目前AC的提交都是CDQ分治。
by meyi @ 2021-06-27 02:20:58
@[zankizero](/user/67942) 谢谢qwq
by zero4338 @ 2021-06-27 07:37:56
@[zero4338](/user/174469) 随机情况下一般叫期望复杂度吧，或者平均复杂度，什么时候均摊复杂度也分情况了？
by damocris @ 2021-12-30 17:14:01