RT,发现自己之前的做法复杂度有亿点问题。。。
复杂度是 O(∑∣S∣nB+m∑∣S∣B)O(\sum|S|\frac{n}{B}+m\sqrt{\sum|S|B})O(∑∣S∣Bn+m∑∣S∣B),之前误以为是 O(∑∣S∣nB+m∑∣S∣B)O(\sum|S|\frac{n}{B}+m\sqrt{\frac{\sum|S|}{B}})O(∑∣S∣Bn+mB∑∣S∣) 取了 B=nB=\sqrt{n}B=n,然而还是跑得比标算快不少
实际复杂度应该是 O(∑∣S∣n+mn4∑∣S∣)O(\sum|S|\sqrt{n}+m\sqrt[4]{n}\sqrt{\sum|S|})O(∑∣S∣n+m4n∑∣S∣) 才对的啊?
但是当我取到正确块长 B=∑∣S∣3(nm)13B=\sqrt[3]{\sum|S|}(\frac{n}{m})^{\frac{1}{3}}B=3∑∣S∣(mn)31 时反而跑得更慢了?
做法是这个 有没有老哥可以帮忙分析一下是哪儿导致了时间爆炸啊/kel