请问此题的复杂度是什么？(注意有题解剧透)

P3350 [ZJOI2016] 旅行者

totorato @ 2018-10-20 22:18:02

网上普遍说复杂度

O((nm)^{1.5}log(nm))

但是我自己算出来：

T(S) = 2T(\frac{S}{2}) + O(S^{1.5}log(S)) T(S) = \sum_{a=0}^{\log_2S}{2^a(\frac{S}{2^a})^{1.5}\log \frac{S}{2^a}} = \sum_{a=0}^{\log_2S}{2^{-0.5a}S^{1.5}(\log S-a)} \leq \sum_{a=0}^{\log_2S}2^{-0.5a}S^{1.5}\log S = S^{1.5}\log^2 S\sum_{a=0}^{\log_2S}2^{-0.5a} \leq S^{1.5}\log^2 S\int_0^{\log_2S}2^{-0.5x}dx = S^{1.5}\log^2 S (-2.89e^{-0.35\log_2S}+2.89) = O(S^{1.5}\log^2S

请问我的计算哪里除了问题呢？

by 萌田薰子 @ 2018-10-20 22:19:44

我%得不能再%了

by BlueArc @ 2018-10-20 22:21:51

@boshi 我除了%还能说什么呢

by totorato @ 2018-10-20 23:13:27

我的确算错了。。。

第4行将S^{1.5}\log S提出时不再该乘上一个\log S：

T(S)\leq\sum_{a=0}^{\log_2S}2^{-0.5a}S^{1.5}\log S =S^{1.5}\log S\sum_{a=0}^{\log_2S}2^{-0.5a} \leq S^{1.5}\log S\int_{0}^{\log_2S}2^{-0.5x}dx =O(S^{1.5}\log S)

by Boring__Zheng @ 2019-08-02 15:11:20

%%%

by wlzhouzhuan @ 2020-06-07 21:31:38

orz %%%

完美解决了我的困惑

by _Famiglistimo @ 2022-03-31 14:53:28

orz %%%

感谢大佬的证明

by ducati @ 2022-05-13 18:38:51

感谢大佬的证明

感觉这个求助帖不是让我们来帮您而是让您来帮我们的 %%%

|