关于点分治
  • 板块学术版
  • 楼主Dtay
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/2/6 18:42
  • 上次更新2023/10/24 01:32:15
查看原帖
关于点分治
380295
Dtay楼主2023/2/6 18:42

一般点分治中合并两个连通块 a,ba, b 复杂度是 O(size(a))\mathcal{O(size(a))} 的,这样总复杂度是 O(nlogn)\mathcal{O(n \log n)} 的。但如果合并复杂度变为 O(size(a)+size(b))\mathcal{O(size(a)+size(b))},那最优能做到 O(nlog2n)\mathcal{O(n \log^2 n)} 或更低嘛?求具体做法。

2023/2/6 18:42
加载中...