T(n) = 2T(n/2) + log n 的解
Solution to T(n) = 2T(n/2) + log n
所以我的递归方程是T(n) = 2T(n/2) + log n
我使用了主定理，发现 a = 2，b =2，d = 1。
这是情况 2。所以解决方案应该是 O(n^1 log n) 这是 O(n log n)
网上看了一下，有的发现是O(n)。我很困惑
谁能告诉我为什么不是 O(n log n) ？
我对主定理中的d不熟悉。 Master Theorem 上的 wikipedia article 指出您需要找到 c = log_b a，临界指数。这里是c = 1。情况 2 要求我们有 f(n) = Theta(n log n)，但实际上我们有 f(n) = log n。相反，这个问题属于情况 1（看看你是否能找出原因！），这意味着 T(n) = Theta(n)，正如你在其他地方发现的那样。
这不应该是案例 2，而是案例 1。
如您所见，T(n) = 2T(n/2) + log n 是 c_crit = log_2(2) = 1 的临界指数，我认为是正确的。但肯定 log n 对于 一些 c < 1 是 O(n^c)，甚至对于所有 0 < c < 1，所以情况 1 适用并且整个事情是 O(n^c_crit) = O(n^1) = O(n).
所以我的递归方程是T(n) = 2T(n/2) + log n
我使用了主定理，发现 a = 2，b =2，d = 1。
这是情况 2。所以解决方案应该是 O(n^1 log n) 这是 O(n log n)
网上看了一下，有的发现是O(n)。我很困惑
谁能告诉我为什么不是 O(n log n) ？
我对主定理中的d不熟悉。 Master Theorem 上的 wikipedia article 指出您需要找到 c = log_b a，临界指数。这里是c = 1。情况 2 要求我们有 f(n) = Theta(n log n)，但实际上我们有 f(n) = log n。相反，这个问题属于情况 1（看看你是否能找出原因！），这意味着 T(n) = Theta(n)，正如你在其他地方发现的那样。
这不应该是案例 2，而是案例 1。
如您所见，T(n) = 2T(n/2) + log n 是 c_crit = log_2(2) = 1 的临界指数，我认为是正确的。但肯定 log n 对于 一些 c < 1 是 O(n^c)，甚至对于所有 0 < c < 1，所以情况 1 适用并且整个事情是 O(n^c_crit) = O(n^1) = O(n).