求助主定理

学术版

FBW2010 @ 2024-09-20 09:43:04

关于我无意间刷到一道初赛题，题意大概是求递归形式为 T(n)=2T(\frac{n}{2})+O(n\log n) 的复杂度，于是直接套用主定理的情况3，算出 O(n\log n)。结果一看答案，竟是 O(nlog^2n)。去复习了一下主定理，又拷问了半天 chatgpt，只知道好像主定理不适用于某些问题，要考虑递归复杂度影响，搞得本蒟蒻更懵逼了。问：

  1. 为什么用主定理无法准确得出这题答案？

  2. 主定理不适用于哪些情况？

  3. 对于主定理不适用的又该如何求解？

by CEFqwq @ 2024-09-20 09:44:47

Cu Ball

by Hagasei @ 2024-09-20 09:48:49

@FBW2010 你套情况三算出来不就是 log^2 吗？

by Hagasei @ 2024-09-20 09:49:17

然后学术方面不建议用 chatgpt。

by _edge_ @ 2024-09-20 09:51:55

没懂，主定理写的不是听清楚的么

by Rain_chr @ 2024-09-20 09:54:31

@FBW2010 这种题是不是你稍微意会一下，

by FBW2010 @ 2024-09-20 09:55:49

@Hagasei 情况三不是 \log_b a<f(n)，得出 O(f(n))=O(n\log n) 吗？

by FBW2010 @ 2024-09-20 09:56:22

@Rain_chr 我知道，但是主定理算出来为什么不太对呢

by Hagasei @ 2024-09-20 09:57:19

@FBW2010 哦哦你是这么排的。那么应该是情况二。你套错了，因为 \log_22=1

by NightDiver @ 2024-09-20 09:58:51

你直接画一个搜索树，发现每层的和是n乘一个系数，这个系数随着层数是

by FBW2010 @ 2024-09-20 10:00:01

@NightDiver 我知道怎么算，只是单纯不太理解主定理罢了

| 下一页