fjy666 @ 2022-06-30 09:44:20
rt，萌新刚学KDT，不会证复杂度求教/kk
by rpdg @ 2022-06-30 10:57:20
对于每一次操作，我们进行 K 次划分，那么点集被划分成 2^{k} 份，一条线最多可以被截到 2^{k-1} 份。
时间复杂度就是 T(n)=2^{k-1}T(\frac{n}{2^{k}})+O(1)=O(n^{log_{2^{k}}2^{k-1}})=O(n^{1-\frac{1}{k}})。
然后进行 q 次操作，复杂度应该是 O(qn^{1-\frac{1}{k}}) 吧
by SFlyer @ 2022-06-30 18:39:09
IAKIOI!