莫队算法分块大小玄学调参指南

两个指针

复杂度 $latex O(u*n+\frac{n^2}{u})$

根据均值不等式, $latex u*n+\frac{n^2}{u}$ 在 $latex u*n=\frac{n^2}{u}$ 时取最小值

即 $latex u=\sqrt{n}$

三个指针(带修)

复杂度 $latex O(u*n+\frac{n^2}{u}+\frac{n^3}{u^2})$

显然, $latex \frac{n^2}{u}<=\frac{n^3}{u^2}$ (作商法)

根据均值不等式, $latex u*n+\frac{n^3}{u^2}$ 在 $latex u*n=\frac{n^3}{u^2}$ 时取最小值

即 $latex u=n^{\frac{2}{3}}$

四个指针(多参数)

复杂度 $latex O(u*n+\frac{n^2}{u}+\frac{n^3}{u^2}+\frac{n^4}{u^3})$

根据均值不等式, $latex u*n+\frac{n^4}{u^3}$ 在 $latex u*n=\frac{n^4}{u^3}$ 时取最小值

即 $latex u=n^{\frac{3}{4}}$

赞(2)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址