2

我们能解决这个 T(n) = 2T( n/2 ) + n lg n递归方程主定理吗？我来自一个链接，他说我们不能在这里应用主定理，因为它不满足任何 3ree 案例条件。另一方面，他采取了另一个例子 T(n) = 27T(n/3) + Θ(n^3 lg n) 并找到了封闭的解决方案theta(n^3logn) 为了解决这个问题，他使用了主定理的第二种情况If f(n) = Θ(nlogba (lg n)k ) then T(n) ∈ Θ(nlogba (lg n)k+1) for some k >= 0 在这里我产生了困惑，为什么我们不能在这里应用第二种情况，而它完全适合第二种情况。 我的想法： a = 2 , b =2; let k =1 then f(n) = theta(n^log_2 2 logn) for k= 1 so T(n) = theta(nlogn) 但是正如上面提到的我们不能应用主定理我很困惑为什么不.

注意：这是由于 f(n) bcz in和 in * * 如果我在这里错了，请纠正我。T(n) = 2T( n/2 ) + n lg n f(n) = nlog nT(n) = 27T(n/3) + Θ(n^3 lg n)f(n) = theta(n^3log n)

4

1 回答 1

2

使用主定理的案例 2 我发现

 T(n) = Theta( n log^2 (n))

您的链接指出，theroem 的案例 2 是：

 f(n) = Theta( n log_b(a))

而从其他几个链接，比如来自 mit的链接，情况是：

 f(n) = Theta( n log_b(a) log_k(n)) for k >= 0
于 2012-10-04T11:43:40.027 回答