在 O(nH(n))\mathcal O(nH(n))O(nH(n)) 的做法上简单加了个倍增优化,然后复杂度便乘了这个柿子:
T(n)=t×(∑i=1nlog⌊ni⌋+nlog∣Σ∣)T(n)=t\times \left(\sum_{i=1}^n \log\left\lfloor\frac{n}{i}\right\rfloor+n\log|\Sigma|\right)T(n)=t×(∑i=1nlog⌊in⌋+nlog∣Σ∣)
显然, 它(0.27s0.27s0.27s) 比 O(n)\mathcal O(n)O(n) 慢,但的确快于 O(nH(n))\mathcal O(nH(n))O(nH(n)) 做法( 0.8s0.8s0.8s )。
所以有神仙教教我怎么算 T(n)T(n)T(n) /kel