求助主定理

学术版

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，只知道好像主定理不适用于某些问题，要考虑递归复杂度影响，搞得本蒟蒻更懵逼了。问：

为什么用主定理无法准确得出这题答案？
主定理不适用于哪些情况？
对于主定理不适用的又该如何求解？

by NightDiver @ 2024-09-20 10:00:30

@FBW2010 主定理我根本不会TAT

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

@Hagasei ？？？不应该 O(n)<O(n\log n) 吗

by _edge_ @ 2024-09-20 10:01:03

@FBW2010 log 忽略的，只比较指数

by FBW2010 @ 2024-09-20 10:03:39

@edge emm，感觉对主定理的理解有些不正确，有没有比较严谨的主定理公式？网上找的有好几个版本

by bs_commander @ 2024-09-20 10:03:49

适用于主丁定理的第二种情况啊

by Hagasei @ 2024-09-20 10:03:56

@FBW2010 主定理分三种情况，

f(n)=O(n^c),c<\log_ba
f(n)=\Theta(n^c\log^kn),c=\log_ba
f(n)=\Omega(n^c),c>\log_ba

而 \Theta(n^1\log n)<\Omega(n^{1+\varepsilon})

by Hagasei @ 2024-09-20 10:04:17

严格的公式去维基百科

by bs_commander @ 2024-09-20 10:04:44

参见这里的第二种情况，在递归基础上加一个log，在复杂度就要加俩

by bs_commander @ 2024-09-20 10:06:32

FBW is bot。

by bs_commander @ 2024-09-20 10:06:57

FBW is bot.