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