algorithm - T(n) = 2T(n/2) + log n 的解

Question

所以我的递归方程是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) 吗？

标签： algorithmtime-complexitycomplexity-theorymaster-theorem

Answer 1

这不应该是案例 2，而是案例 1。

正如你发现的那样，我认为T(n) = 2T(n/2) + log n关键指数是c_crit = log_2(2) = 1正确的。但肯定log n是O(n^c)对某些人 c < 1，甚至对所有人0 < c < 1，所以情况 1 适用，整个事情都是O(n^c_crit) = O(n^1) = O(n)。