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

  • A+
所属分类:代码笔记 信息技术

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

两个指针

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

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

即 \(u=\sqrt{n}\)

三个指针(带修)

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

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

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

即 \(u=n^{\frac{2}{3}}\)

四个指针(多参数)

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

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

即 \(u=n^{\frac{3}{4}}\)

xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: