关于此题数据()
查看原帖
关于此题数据()
160839
Prean楼主2022/4/5 10:54

RT,发现自己之前的做法复杂度有亿点问题。。。

复杂度是 O(SnB+mSB)O(\sum|S|\frac{n}{B}+m\sqrt{\sum|S|B}),之前误以为是 O(SnB+mSB)O(\sum|S|\frac{n}{B}+m\sqrt{\frac{\sum|S|}{B}}) 取了 B=nB=\sqrt{n},然而还是跑得比标算快不少

实际复杂度应该是 O(Sn+mn4S)O(\sum|S|\sqrt{n}+m\sqrt[4]{n}\sqrt{\sum|S|}) 才对的啊?

但是当我取到正确块长 B=S3(nm)13B=\sqrt[3]{\sum|S|}(\frac{n}{m})^{\frac{1}{3}} 时反而跑得更慢了?

做法是这个 有没有老哥可以帮忙分析一下是哪儿导致了时间爆炸啊/kel

2022/4/5 10:54
加载中...