关于回滚莫队的块长
  • 板块学术版
  • 楼主Christophe_
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/2/2 09:57
  • 上次更新2023/10/28 09:50:12
查看原帖
关于回滚莫队的块长
335552
Christophe_楼主2022/2/2 09:57

请问回滚莫队的块长到底应该设置为多少?如果设有 n 个数,询问次数为 m,网上直接设为 sqrt(n) , 导出复杂度为 O((n + m) * sqrt(n));但是是否应该设置为 n / sqrt(m) 才能达到更优的复杂度 O(n * sqrt(m)) ?因为设块长为 t ,则易得复杂度为 O(m * t + n * n / t) >= O(2 * n * sqrt(m)) = O(n * sqrt(m)) ,当且仅当 mt = n * n/ t 时取等,此时 t = n / sqrt(m).

2022/2/2 09:57
加载中...