T(n) = 27T(n/3) + (n^3)log(n) 的时间复杂度
Time complexity of T(n) = 27T(n/3) + (n^3)log(n)
我需要一些帮助来解决这种复发问题。我自己试了一下，得到了 teta( (n^3)logn) 但 Wolfram Alpha 是这样说的：
我想这就像一个
O（（n^3）log^2（n））。我不会用大定理，所以我用递归的方法解决了。这是我的解决方案，但我不知道它有什么问题
你在最后阶段犯了一个错误。使用这些属性：log(x) + log(y) = log(xy) 和 log(x/y) = log(x) - log(y) 以及 log(x^y) = y log(x)`，我们有以下内容：
sum_{i=0}{k-1} log(m/3^i) = log(m^k / (1 * 3 * 3^2 * ... * 3^(k-1)))
= log(m^k) - log(3^((k-1)k/2))
= k log(m) - (k-1)k/2 log(3) = c * k * (k-1) = Theta(log(m) * log(m))
因此，时间复杂度为m^3 log^2(m)。
我需要一些帮助来解决这种复发问题。我自己试了一下，得到了 teta( (n^3)logn) 但 Wolfram Alpha 是这样说的：
我想这就像一个 O（（n^3）log^2（n））。我不会用大定理，所以我用递归的方法解决了。这是我的解决方案，但我不知道它有什么问题
你在最后阶段犯了一个错误。使用这些属性：log(x) + log(y) = log(xy) 和 log(x/y) = log(x) - log(y) 以及 log(x^y) = y log(x)`，我们有以下内容：
sum_{i=0}{k-1} log(m/3^i) = log(m^k / (1 * 3 * 3^2 * ... * 3^(k-1)))
= log(m^k) - log(3^((k-1)k/2))
= k log(m) - (k-1)k/2 log(3) = c * k * (k-1) = Theta(log(m) * log(m))
因此，时间复杂度为m^3 log^2(m)。