Loading...

关于分块最优块大小的思考

check评论:0 条 remove_red_eye浏览量:599 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-29

说到可爱的分块算法,我们都知道它的复杂度为$O(\sqrt n)$,所以一般的,我们设块的大小$block=\sqrt n$

然而有的时候发现,对于真正的随机数据,这种块大小可能并不能很好的完成任务,甚至可能常数被卡的非常大,于是我们开始思考,如何去优化分块,用改变块的大小的方式来进行优化

  • 随机数据每次操作期望的长度

我们现在来问个问题,一个长度为$n$的序列,随机取出一个区间,其期望长度是多少?

你可能会很容易的想出一个看似很正确的错误答案$\frac{\sum_{i=1}^n i}{n}$

然而这是错的qwq,因为一种长度可能在序列的任意地方出现,也会影响到跨过的块的个数

举个例子,当$n=4$时,用之前的算法得到的答案是$2.5$

而我们真正可以分得的区间有$1-1,2-2,3-3,4-4,1-2,2-3,3-4,1-3,2-4,1-4$

也就是说期望的答案应该是$(1*4+2*3+3*2+4*1)/(1+2+3+4)=2$

那么,我们可以得到答案应该是$\frac{\sum_{i=0}^{n-1} (n-i)*(i+1)}{\sum_{i=1}^n i}$

化简后得到答案$\frac{n+2}{3}$,则块的大小应该是$\sqrt{\frac{n+2}{3}}$,事实证明这种分块方法的确能够很好地应对随机数据

  • 其他的分块大小

博主常用的大小还有$block=\sqrt{\sqrt{n}+m}(m>\frac{n}{4}),block=\sqrt{n}(m \leq \frac{n}{4})$,这种方法虽应对随即数据没有上面介绍的优秀,但在一些情况下还是很好的了。

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名