Cu Ball
by CEFqwq @ 2024-09-20 09:44:47
@[FBW2010](/user/906072) 你套情况三算出来不就是 log^2 吗？
by Hagasei @ 2024-09-20 09:48:49
然后学术方面不建议用 chatgpt。
by Hagasei @ 2024-09-20 09:49:17
没懂，主定理写的不是听清楚的么
by _edge_ @ 2024-09-20 09:51:55
@[FBW2010](/user/906072) 这种题是不是你稍微意会一下，
$2T(\frac n2)$ 显然是分治，$O(n\log n)$ 就很像是树状数组，分治+树状数组容易想到cdq分治解三维偏序，这就是两个log的经典算法了。
by Rain_chr @ 2024-09-20 09:54:31
@[Hagasei](/user/383785) 情况三不是 $\log_b a<f(n)$，得出 $O(f(n))=O(n\log n)$ 吗？
by FBW2010 @ 2024-09-20 09:55:49
@[Rain_chr](/user/684254) 我知道，但是主定理算出来为什么不太对呢
by FBW2010 @ 2024-09-20 09:56:22
@[FBW2010](/user/906072) 哦哦你是这么排的。那么应该是情况二。你套错了，因为 $\log_22=1$
by Hagasei @ 2024-09-20 09:57:19
你直接画一个搜索树，发现每层的和是n乘一个系数，这个系数随着层数是
$\sum_{i}^{\log n} i$ 的，与 $(\log n)^2$ 同级
by NightDiver @ 2024-09-20 09:58:51
@[NightDiver](/user/985711) 我知道怎么算，只是单纯不太理解主定理罢了
by FBW2010 @ 2024-09-20 10:00:01