主题

主题

 
   

关于分块的块大小

  • 扯淡

以前都是O(sqrt(n))的块。然后现在面临被卡常的风险。

本来1e5的数据应该是支持O(nsqrt(n))=O(nlog^2n)的。

但是由于分块这个常数有点危险,所以我们还是要考虑考虑。尤其是在分块还要带log的情况下,就不得不警惕了。


  • 分析

可以类似莫队复杂度分析得到。

假设我们的块的大小是Threshold,块的个数是Num。Num*Threshold=n。


根据双勾函数的性质,令此函数最小。此时:


即:

Threshold=sqrt(0.5*n*T(block)/T(sca))

复杂度为

O(sqrt(2*n*T(block)*T(sca)))


  • 与Threshold=sqrt(n)的区别。

区别是很明显的。

我们用常用到的,T(block)=logn来计算。

那么合理分块的复杂度是从O(sqrt(n)logn)变为了O(sqrt(nlogn))。那么就是把17变为了4。这样使得分块的速度大大提高。


  • 对于T(block)=T(sca)的思考

发现这样一来完全没有任何的优化。不能通过调整块的大小来加速。于是这样就是妥妥的O(sqrt(n)logn)了。

那么就需要优化算法,除非数据范围小。


  • 对于纯暴力的思考

如果T(block)=O(Threshold)呢?那么这是一个纯暴力。

自然并不是上面看上去的O(sqrt(nsqrt(n)))。

显然是O(n)的。于是这样就退化了。

可见并不是T(block)与T(sca)相差越大越好。

 
 
评论
 
 
热度(1)